1、Overview題目名稱尋找 yyyyCosmic StackerWAV-MIDI題目代號Prob1Prob2Prob3Prob4輸入文件名Prob1.inProb2.inProb3.inProb4_0.in Prob4_9.in輸出文件名Prob1.outProb2.outProb3.outProb4_0.out Prob4_9.out每個測試點時限3 秒2 秒10 秒N/A測試點數(shù)目10101010每個測試點分值10101010是否有部分分無無無有題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)結(jié)果提交1、尋找 YYYY 跑到了一個森林里藏了起來。這下可急壞了 BB?！癥”是這樣的形狀：以一個點為“根”，根上連接著三

2、條長度不為 0 的鏈，且這三條鏈除了根以外沒有其它公共頂點。顧名思義，“YY”就是兩個不包含公共節(jié)點的“Y”了。不是一個Y是一個 Y 是一個Y不是一個Y是一個 YY不是一個YY任務就是，給定一個森林（森林就是一張無環(huán)的無向圖），讓你在里面找到 YY。BB 認真觀察了一下森林的形狀，發(fā)現(xiàn)里面包含了好多 YY。好在還有一個線索，YY 的體積比較大，所以各條邊長度和最大的 YY 最可能是 BB 要找的 YY。別忘了 YY 喜歡去“大榕樹”，因此有可能整個森林就是一顆樹。 YY 的兩個“Y”可能分布在兩棵樹上，也可能在同一棵樹上。 輸入格式：第一行兩個正整數(shù)N 和 M，分別表示森林里的點數(shù)和邊數(shù)。0M

3、N=106。后面 M 行，每行有三個整數(shù) A,B,C，表示 A 和 B 之間有一條長度為 C 的邊。頂點到 N。邊的長度不超過 103。輸出格式：從 1輸出文件只有一行，這行只有一個正整數(shù)，即森林中 YY 的各條邊長度和的最大值。如果森林中沒有YY，輸出一行：“POOR BB”（不包括引號）。樣例輸入：11 91 2 33 4 64 5 54 6 56 7 36 8 48 9 39 10 99 11 7樣例輸出：38樣例說明：樣例輸入輸出對應下圖：5365 43379尋找 YY的題解算法一（我出此題時的算法，即標程算法）首先，毋庸置疑的，森林當然是一棵棵樹考慮，要么 YY 出現(xiàn)在某棵樹上，要么

4、兩個 Y 分別出現(xiàn)在兩棵樹上，不管是哪一種情況，在每棵樹上的情況考慮完以后就不難處理了。因此只需要考慮一棵樹的情況。一棵樹上的Y：對每個節(jié)點 i 計算 3 個值 Ai,Bi,Ci，分別表示以下 3 種情況的總長度：iiiiBCAA 是向下引了一條鏈，而 B 是已經(jīng)向下引了兩條鏈，并且上面還可以連接。C 是自己的兒子中連出了一個 Y 型，但并不與自己相連接，或雖然與自己相連接，確不能繼續(xù)向上連。 轉(zhuǎn)移的過程：A：由某個兒子的A 得到。即 Ai=maxAj+disti,j,fatherj=i。B：可以由兩個兒子各拉一條鏈（即兩個A）得到，也可以由某個兒子的 B 得到。C：可以由 3 個兒子各拉一條

5、鏈（即 3 個 C）得到，或者一個兒子的 B 及一個兒子的A，或者一個兒子的 C 得到，當然，如果是由一個兒子的 C 得到，是不能加上這一條邊的長度的。Croot還是 maxBroot,Croot？后者肯定不對，因為有這樣的情最后的結(jié)果是況也算作 B：root但是如果選擇前者，好像前者并不能涵蓋所有情況。的確，剛才對 C 的定義是：已經(jīng)形成了一個 Y，且不能往上繼續(xù)連接。因此如果“還能繼續(xù)向上連接”就不被考慮了。解決辦法就是，把這種情況也考慮進去！小結(jié)：3 個狀態(tài)，遞推關(guān)系：如果覺得這個算法不算過于的話，那么就開始直接的擴展吧！如果在一個樹中出現(xiàn)了兩個Y，可以分 6 種情況，前 3 種與剛才介

6、紹的一致，后三種 D，E，F(xiàn) 分別類似于 A，B，C 但中都比原來多包含了一個完整的Y。AAj+disti,jBAj+disti,j+Ak+disti,kBj+disti,jCAj+disti,j+Ak+disti,k+Al+disti,lBj+disti,j+Ak+ disti,kBj+disti,jCj它們的遞推關(guān)系：這個動態(tài)規(guī)劃的復雜程度大大超出了來。應該注意以下幾點：的預期，然而在關(guān)系之后還是有可能寫得出1、n 很大，要注意時間復雜度要控制在 O(n)。注意到需要的無非是 Aj+disti,j，Bj+disti,j，Cj，Dj+disti,j，Ej+disti,j，F(xiàn)j最大的幾個兒子節(jié)

7、點，更準確的說，僅僅需要算出這 6 個數(shù)前 4 名的兒子節(jié)點。2、要注意兒子的問題，上面給出的各個式子中 j,k,l,m 都表示 i 的不同兒子節(jié)點，因此轉(zhuǎn)移的時候不能選取重復的兒子，比如選擇了Aj+disti,j，又選擇了 Bj+disti,j，這顯然是錯誤的。為此，需要專門使用循環(huán)來判斷。好在只保存前 4 名，這都只是常數(shù)，而且可以進行一些必要的常數(shù)優(yōu)化。3、和第 4 次比賽的 l需要使用棧模擬等辦法。s 一樣：1000000 個節(jié)點的樹如果使用遞歸遍歷會棧溢出。不難看出，如果只有一個 Y 的話，這樣的動態(tài)規(guī)劃還算令人接受，但是有兩個 Y 的情況就讓人受不了了。能不能避免考慮兩個Y 的情況

8、呢？是能！DCj注：Cj不能直接往上連接，但是 j 的父親 i 可以繼續(xù)往上連接以第二個yDj+disti,jAj+disti,j+Ck+disti,kEEj+disti,jAj+disti,j+Ak+disti,k+ ClAj+disti,j+Dk+disti,kBj+disti,j+Ck+disti,kFFjEj+disti,j注：這個的理由和 Ci可取 Bj+disti,j一樣Cj+CkAj+disti,j+Ak+disti,k+Al+disti,l+CmAj+disti,j+Ak+disti,k+Dl+disti,lAj+disti,j+Ek+disti,kBj+disti,j+CkB

9、j+disti,j+Dk+disti,kAj+disti,j+Bk+disti,k+Cl+disti,l替代算法這個是樣例中的主要的那棵樹?？梢钥吹?，中間有一條沒有被選取的邊。而且，只要兩個 Y在同一個樹上，就必然會存在某個邊，在刪除這條邊之后兩個Y 屬于不同的。這樣，任何一個函數(shù) f(i)就可以改成每條邊(i,j)計算兩個狀態(tài)：f(i,j)和 f(j,i)。f(j,i)表示以 j 節(jié)點作為 i 的父親節(jié)點時，以 i 為根的的f(i)。這樣，只要對于每條邊(i,j)計算 A(i,j), B(i,j), C(i,j), A(j,i), B(j,i), C(j,i)即可。然后，對于計算 maxC(

10、i,j)+C(j,i)，就是這個樹上的兩個 Y 的最大的總長度。：時間復雜度在情況是 O(n2)的！為什這個辦法看似簡潔，但是又遇到了一個新么？考慮一個度很大的結(jié)點 v，它的度數(shù)大到了與節(jié)點數(shù) n 同階。v那么對于每一個(i,v)，都需要分析所有的(v,i)才能得出。這樣，時間復雜度就是 O(D2)=O(n2)的了。而事實上，我在制作數(shù)據(jù)的時候考慮了這一點，有不少數(shù)據(jù)點都強化了點的度數(shù)。而 O(n2)在時間上的缺陷也充分了出來。能不能找出一個既相對簡潔，又能在 O(n)時間內(nèi)完成的算法呢？還是能！算法二這個算法有點像冬令營中的例題 4 的子問題 2。不妨去參見那篇。不同點只是那篇是對Hash

11、函數(shù)的遞推，而這里是動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移。簡要地介紹一下，隨便找一個節(jié)點作為根節(jié)點，然后dfs，則可以在O(n)時間內(nèi)求出所有滿足 dist(i)=dist(j)-1 且(i,j)E 的A(i,j),B(i,j)和 C(i,j)。換句話說，有了根之后，這棵樹有了“上下”的概念，對于所有 i 在 j“上面”的狀態(tài)已經(jīng)可以計算出來了。然后再進行第二次 dfs，和第一次從同一個根節(jié)點出發(fā)。不同的是第一次 dfs 是后序的（處理完兒子節(jié)點才能再處理自身），而這一次是先序地先處理自己再處理兒子節(jié)點。第二次 dfs 時，每個節(jié)點 v 時對于所有與 v 相連的點 u，A(v,u), B(v,u)和 C(v,u

12、)都已被計算出了。這樣，可以分別保存使 A(v,u), B(v,u)和 C(v,u)取到的前 4 大結(jié)果的 u。然后可以計算出所有的形如 f(u,v)的狀態(tài)，因為可以4 名的列表里去掉和 v 有關(guān)的，得到“和 v 無關(guān)的前 3 名”，然后利用它算出 A(u,v), B(u,v)和 C(u,v)。這一步的總時間復雜度還是O(n)。至此，用可以接受的時間復雜度和編程復雜度完成了此題。盡管代碼還是較長，但是出錯的幾率和思維的復雜程度都大大降低了。2、YY做了 AHOI2006 的 Board 一題，YY 覺得天昏地暗，回腸蕩氣，繞梁YY 也就想出了一個問題：對于一個完全二分圖，有多少種不同的完備匹配

13、？結(jié)果 YY 發(fā)現(xiàn)這個問題太簡單了，根本難不倒大家。YY 就改進了一下，對于一個有 2N 個節(jié)點的完全二分圖，包含邊數(shù)為 0，為 1，為 2為 N 的匹配分別有多少？YY 經(jīng)過研究，發(fā)現(xiàn)此題存在 N 種解法，甚至可以交表！絕望的 YY 心想，這下子傷自尊了，題目沒法出了。好在他這時突然又想起了 Board 那題?！皩Π?！”YY 說，“我在圖中刪去 M 條邊，再問匹配分別有多少，這樣就沒辦法交表了?！卑厰?shù)為 0，為 1，為 2為N 的于是，問題就出來了?？上У氖牵@下子 YY 真的不會做了大家會做的話幫一下YY 吧。輸入格式：第一行兩個整數(shù) N 和 M，定義見上文。1=N=500，0=M=對

14、于一個給定的局面，YY 想知道能否將所有圈圈消除。因此，請你設計一個程序幫他判斷。注：1、消除的時候，只要移動后是三個同色圓環(huán)相套即可?？梢允且苿右粋€圓環(huán)到兩個圓環(huán)的位置上，也可以是移動兩個圓環(huán)到一個圓環(huán)的位置上。2、移動和消除造成的空隙會自動因為圓圈的移動而彌補。3、移動的時候，是先把待移動的圓圈拿起來（這時與它相鄰的圓圈就接觸了），然后再放在目的地上。因此，這樣的移動會導致這一排全部消除：輸入格式：每個輸入文件包含了若干組數(shù)據(jù)。因此輸入文件第一行有一個正整數(shù) T，表示數(shù)據(jù)的組數(shù)。（1=T=10）。對于每組數(shù)據(jù)：第一行是兩個正整數(shù) N 和 C。表示現(xiàn)在一共有 N 個圓圈，包括了 C 種顏色。

15、1=N=15，1=C=5。后面有 N 行，第 i 行有兩個正整數(shù) Ai 和 Bi，Ai 表示這個圓圈的尺寸（0 是最小號的，1 是中等的，2 是那種最大的），Bi 表示這個圓圈的顏色（1=Bi MIDIYY 喜歡MIDI。MIDI 容量小，音質(zhì)好，而且不會有討厭的歌詞（這也算是優(yōu)點？）。因此，YY 超級喜歡聽 MIDI?，F(xiàn)在能弄到的音樂文件大多不是 MIDI 格式的，而往往是 MP3或者 WMA 格式的。YY 把它們處理成了 WAV 格式，希望你幫個忙。問題簡化以后是這樣的：認為 MIDI 中有K 種樂器，波形都是已知的。一段樂譜了若干個音符，整個音樂的波形就是各個音符的波形的疊加。這里，“波

16、形”都是由一連串的非負整數(shù)表示的。對于長度為 L 的一個波形，時刻 1、時刻 2時刻L 的波幅都是非負整數(shù)。相鄰時刻之間的波形是一條線段（因此，比較兩個波形是否相同只需要比較整數(shù)時刻的波幅是否相同即可）。在時刻 1 之前和時刻 L 之后的所有整數(shù)時刻的波幅都是 0。對于給定的音樂波形和樂器波形，請輸出一段正確的樂譜，樂譜的長度應盡量短。輸入格式：第一行一個K，表示樂器的種類數(shù)。后面一行是整個音樂的波形。然后 K 行是 K 種樂器的波形。每個波形的格式都是這樣的：第一個數(shù)字表示這個波形的長度 L，后面 L 個非負整數(shù)，表示這個波形。為了保證有解，YY 保證存在某種樂器的波形是長度和幅度都為一。輸

17、出格式：第一行一個N，即音符個數(shù)。（N MIDI題解首先，由于本題題目描述比較冗長，第一步要做的應該是理解題意。由題目描述不難發(fā)現(xiàn)，其實本題問題本身很簡單，就是給定一些數(shù)字串，可以進行任意的偏移以后進行相加，而目標是用最少的數(shù)字串拼出給定的目標串。由于很顯然不可能搜索出全部數(shù)據(jù)的結(jié)果，只能求助于近似算法。隨機化貪心，作為兼具貪心的“智能”特點和隨機化算法可以多次求解以求更優(yōu)的特點的算法，成為選擇。的最佳然后還有一些優(yōu)化可以使用：1、雖然保證提供一個樂器的波形是 1 1，但是很顯然這種樂器使用多了會使解變差，因此我們得到第一個來自的想法：盡可能先選擇數(shù)字和比較大的串。2、從邊緣入手。觀察第 2 組，第 9 組等比較“稀疏”的數(shù)據(jù)的兩端，不難發(fā)現(xiàn)很容易“猜”到應該選擇哪些串效果比較好