百度NOIP吧編程挑戰賽 解題報告

測試數據：點此下載

作弊名單：點擊查看

比賽成績：點此查看

第二題 Special Judge 程序下載：點此查看

（解題報告由出題人或選題人提供。）

1、這也叫破譯？

problem：輸入n個字符串，統計權值，按權值降序排序，輸出字符串和權值。

analyze： 作為模擬賽的第一題，難度很easy啊。沒有什麼難的地方，很基本的算法，ac不成問題。

project：加強字符串的讀入和統計能力，快速排序的能力和記錄類型的運用。

用table數組表示字母表,直接定義成常量數組：table:array

\[97..122\]

of integer=();這樣在可以定義一個函數cost，表示每個單詞的權值。

a

\[i\]

.data記錄每個字符串，a

\[i\]

.cost記錄每個字符串的權值，通過1個qsort(用隨機化快排還是很棒的（隨機化快排是什麼？百度一下），進行排序，排完序輸出。

2、聯絡

本題很明顯屬於圖論中的求最小生成樹，只需要注意把存在的邊權值賦為0即可。

3、衝鋒

菜鳥：NPC_T

Charge這道題準確的說並不是我的原創（我的原創部分由於和第二題的考察範圍衝突和諧掉了），而是改編自CTSC`98的題目選課（score）。唯一不同的是，由於時代的進步，本題大大增加了數據範圍，由原題的n、c小於400大大增加。

先簡單地說一下題目的建模分析：題目已經闡述得很清晰，這明顯是一個樹，從樹中選出若干個點（選這些點的充要條件是他們的父親被選）並最大化點權之和。很容易想到這是一個樹形DP，物品就是這些節點，其重量為1，價值為點權。

用傳統的樹形DP（如DDengi牛在《揹包九講》一文中所講述）可以做到O

(n*C^2)，其基本思想是引入「泛化物品」的概念，即f

\[i,j\]

表示在以點i為根的子樹中耗費重量j所能得到的最大價值；由於該方法簡單容易理解且大多數人都已經看過，加上n*C^2的算法明顯對於這道題會死的很慘（60~80分），我談一下樹形DP的O(nC)算法（該算法複雜度已經達到樹形DP問題的理論下界，證明略）。

首先鳴謝2008年的noi金牌第九名，現就讀於徐持衡(xc_bb)大牛，是他的WC2009國家集訓隊論文《淺談幾類揹包題》讓我首次認識這種優秀而簡潔的算法，這次命題也得到了他本人的幫助，核心思想也來自他的論文。

如果說DDengi的「泛化物品和」算法已經深入挖掘了「揹包」這一名詞的本質，那麼xc_bb的「泛化物品並」算法就是對「最優化」的細細推敲。其基本思想是，如果有f

\[i\]

,f

\[k\]

兩個泛化物品，那麼他們的最優泛化物品並應該是

f

\[i,j\]

=max{f

\[i,j\]

,f

\[k,j\]

}

這個關係簡潔而明顯，在此不需要多說。而接下來的結論顯然更驚豔一些：對於一個節點i和它的一個兒子x，我們先將f

\[i\]

強制賦給f

\[x\]

，然後遞歸地解決x，最後f

\[i\]

就是原來的f

\[i\]

和而今的f

\[x\]

的泛化物品並。

當然這個描述過於「泛化」，鑑於本菜鳥水平有限，無法將其特別明晰地表述清楚（其實我理解這個也花了整整一節歷史一節地理的時間），現附上xc_bb大牛的《淺談幾類揹包題》神文地址，相信大家從中可以學到很多，不僅僅是樹形揹包，對於其他各類揹包也會有一個更深刻的理解。

以下是神文的度娘文庫地址：

http://wenku.baidu.com/view/8ab3daef5ef7ba0d4a733b25.html 【pdf】

http://wenku.baidu.com/view/3fd4138884868762caaed5a8.html 【ppt】

感謝國家，感謝黨，感謝noip貼吧提供給我這次命題的機會，感謝父母，感謝xc_bb大牛，感謝各位來參加模擬賽的oier們！

4、開燈關燈

這個題看起來好你是bfs，但是對於普通的bfs來說，數據過大一定超時。這裡我們注意到終結狀態是一定的，於是我們考慮把所有可能的初始狀態都求出來，記錄每一個點到達終結狀態的過程，然後打表輸出，那麼整體的時間效率就看求初始狀態的時間了，當然我們就不能直接bfs了，但是我們可以從終結狀態向回查找，每回一步得到的狀態都進行記錄，這樣就完成了查找過程。

可能我寫的不太好，大家不太好理解，大家都看一下程序就好了……