NOIP2010提高組解題報告2

1、1. translate（20分）簡單模擬。開一個1000的隊列，時刻保持隊列長度不大于M，每次接受翻譯請求時，先在隊列中查找，查找失敗則將單詞加入隊列。查找使用Hash則為O(N)，直接掃描O(MN)，都在可接受范圍內(nèi)?？荚嚂r只打了20分，原因至今不明，告誡大家對于水題不要多想，就像這道題最好不開hash，因為一個系統(tǒng)的可靠度是該系統(tǒng)所有子系統(tǒng)可靠度之積，程序越復雜越可能出錯。2. tortoise（50分）基礎(chǔ)動規(guī)。可以從題目背景中抽象出這樣的問題：有一四維立方體（這里的立方體棱長不必相等，每一維對應一種卡片，每維的棱長對應該種卡片個數(shù)），每走一格（即使用一張卡片）的收益是當前位置坐標的函

2、數(shù)。求從(0,0,0,0)走到(a1,a2,a3,a4)最大收益。故有方程fx,y,z,t=maxfx-1,y,z,t, fx,y-1,z,t, fx,y,z-1,t, fx,y,z,t-1 + w1 + x + y*2 + z*3 + t*4目標狀態(tài)： fa1,a2,a3,a4O(b4)的代價，數(shù)據(jù)保證b<=40,完全滿足要求3. prison（70分）問題可以重新描述為：尋找最小的沖突值c，使得存在一種方案，將原圖分為兩部分，并去掉這兩部分之間的所有邊后，余下的邊權(quán)都不大于c。對于這個問題我們可以二分查找c，并判定其可行性。判定可行性的方法至今沒想好。考試的時候我是用并查集，將所有與

3、u相連并與u之間邊權(quán)大于c的點（設為點集Zu）必然不與u在同一集合中，枚舉所有的u，每次將Zu合并成為一個集合，若存在某點u和Zu某個點處于同一個集合中，則c不可行，反之則可行。但這種方法貌似存在bug，能拿70分。如果把并查集合并查找的時間代價看作常數(shù)，則這種做法的時間代價為O(elogK),e是邊數(shù)，K為最大的沖突值。4. flow（100分）123456U D先用floodfill預處理出上方的每個格子能覆蓋到下方的格子，構(gòu)造一個布爾矩陣，行下標表示最上方的某個點，列下標表示最下方的某個點，矩陣對應點的值表示相應兩個點的覆蓋關(guān)系。回想BYTELAND射擊競賽一題，可以發(fā)現(xiàn)這道題是有貪心策

4、略的。為了描述方便，這里把布爾矩陣看作一個二分圖U-D的壓縮鄰接矩陣，其中最上方與水源相鄰的點集為U，下方與沙漠相鄰的點集為D。如果D中某個點入度為0，則不存在合法的建立方式。1234561234561TTFFFF2FTFFFF3FTTTFF4FTTTTF5FFFFTF6FFFFTT貪心策略：A. 每次選擇D中入度最小的，設為u。B. 選擇U集合中與u相連并且出度最大的點v。C. 在v處建立水源設施，并從二分圖中刪去v和與v相連的所有點、邊。D. 重復ABC，直至D集合為空可以證明，以這樣的貪心策略構(gòu)造的建立方式一定是最優(yōu)的。這樣，floodfill時間代價O(NM2)（可以通過記憶化優(yōu)化至O

5、(NM)，但不是很必要）,貪心部分最多執(zhí)行M次，每次貪心需要掃描出入度表和布爾矩陣的一行一列，時間代價O(M2),總的時間代價在立方級，勉強可以接受。時間分配（可以看出很不合理）：translate : 5mintortoise : 110minprison : 10minflow : 30min考試感言：NOIP10難度和去年相仿，思維量可能略大一些。去年缺席的動規(guī)今年回歸，表明動態(tài)規(guī)劃仍是NOIP的重要考點。1、2兩題杯具了，導致整套題分數(shù)拉低了不少，沒進省隊，有點遺憾。不過拿1=走人也是個不錯的選擇。就當我是在DP吧，局部次優(yōu)解導致了全局最優(yōu)解。這次我的時間分配不夠合理。開始讀題的時候把第二題當作多重背包了，所以打算30min內(nèi)刷完1、2兩題。等到上手第二題的時候才發(fā)現(xiàn)思路不正確。然后我的思路就被局限在了背包問題上，之后的三、四題的編碼過程都是穿插在第二題的思考過程中的。但是到最后也沒想出來第二題的正解，反而耽誤了很多檢查時間，最后剩20min的時候我才決定把第二題定型在50分程序上。這也間接導致了我由于沒時間出有技巧的測試數(shù)據(jù)而在第一題上栽跟頭。再說一句，寫DP方程一定要查冗余狀態(tài)，我做第二題的時候的最終思路類似正解，但多加了一個冗余狀態(tài)，即距出發(fā)點