答案提交題目解題方法

1、By Nettle答案提交題目解題方法什么是答案提交題目在NOIp以上難度的比賽中，我們會(huì)遇到這樣一類題：題目描述的是一道時(shí)間復(fù)雜度很高的NP問(wèn)題或是一道NPC問(wèn)題，通常情況下這類題目存在多個(gè)解，而你的目的是去找出其中的最優(yōu)解。顯然，這樣的問(wèn)題是不可能在短時(shí)間內(nèi)通過(guò)程序得到最優(yōu)解。不過(guò)這類題會(huì)把輸入文件給選手，選手只需要在比賽過(guò)程中計(jì)算出給定的輸入文件的解即可得分，具體的分?jǐn)?shù)需要通過(guò)選手的解和最優(yōu)解進(jìn)行計(jì)算。由于最后提交的是每個(gè)輸入文件的解，所以我們稱這一類的問(wèn)題為答案提交的題目。答案提交的題目一般包含下面幾個(gè)東西：題目：和傳統(tǒng)題目相同的描述輸入文件：若干個(gè)in文件Check程序：某些題目中用

2、來(lái)檢查選手輸出文件是否合法的程序 NOI 2004 畢業(yè)生(graduate)在一個(gè)二維平面上，給定一些積木。要求將積木按照一定的方式擺放，再用一個(gè)矩形將其圍起來(lái)，目的是使矩形的面積最小。graduate1.ingraudate2.inCheck程序的使用Windows系統(tǒng)下：在命令行cmd中，進(jìn)入存放.in和.out文件的文件夾，此時(shí)須保證check程序也在該文件夾，調(diào)用命令：check Linux系統(tǒng)下：在終端中，進(jìn)入存放.in和.out文件的文件夾，同樣須保證check程序存放在該文件夾，調(diào)用命令：./check 其中表示測(cè)試數(shù)據(jù)的編號(hào)。調(diào)用命令不一定是上面兩種，需要根據(jù)題目說(shuō)明決定。但

3、是調(diào)用時(shí)當(dāng)前目錄一定要為數(shù)據(jù)文件夾。答案提交題目常用解題方法借助圖畫、記事本等工具手算寫搜索程序，算可行解(答案提交的題通常提交即可得1分)非完美程序，針對(duì)特殊數(shù)據(jù)寫特殊算法啟發(fā)式搜索借助圖畫、記事本等工具手算通常情況下，所有提交答案的題目前23個(gè)點(diǎn)數(shù)據(jù)范圍都比較小，可以手算。比如說(shuō)剛剛看過(guò)的題目畢業(yè)生，此題前5個(gè)點(diǎn)均可以通過(guò)觀察數(shù)據(jù)進(jìn)行手動(dòng)驗(yàn)證，大概花上1個(gè)小時(shí)能夠拿到4050分。在NOI考場(chǎng)上是會(huì)發(fā)放草稿紙的，不夠了應(yīng)該還是可以繼續(xù)要。所以多動(dòng)動(dòng)筆就能夠拿到一定的分?jǐn)?shù)。搜索程序搜索程序可以拿到基本分。對(duì)于某些有解即可得分的題目，可以考慮搜索算法，求出任意一個(gè)可行解，這樣可以至少保證拿到1分

4、。如果Rp比較好，也有可能拿到5分以上。這一類的題目有：NOI 2007 調(diào)兵遣將NOI 2006 聰明的導(dǎo)游NOI 2002 新俄羅斯方塊非完美程序非完美程序是用處較大的一種方法。由于出題人通常都會(huì)弄至少一組特殊數(shù)據(jù)，所以我們?nèi)绻軌蚺袛喑鲞@些數(shù)據(jù)，并對(duì)其進(jìn)行分析，寫出針對(duì)算法，此類數(shù)據(jù)點(diǎn)基本上能夠拿到810分，某些題目點(diǎn)甚至有可能拿到1112分。這里以NOI 2010 成長(zhǎng)快樂為例來(lái)講：NOI 2010 成長(zhǎng)快樂(Nemo)Nemo是一條無(wú)憂無(wú)慮的小魚，它的初始體重為w0?？蓯鄣腘emo希望自己能夠盡快地成長(zhǎng)，因此需要吃盡量多的食物。Nemo最喜愛的食物是海里的小蝦。已知Nemo對(duì)食物的情

5、況了解如下：大海里共有n只小蝦，從1到n編號(hào)，其中編號(hào)為i的小蝦的重量為wi。將大?？醋饕粋€(gè)X-Y坐標(biāo)系，在0時(shí)刻編號(hào)為i的小蝦所在的位置為(xi, yi)。小蝦在大海中作勻速直線運(yùn)動(dòng)，其中編號(hào)為i的小蝦的速度向量為(pi, qi)，即在時(shí)刻t，它的位置為(xi+pi*t,yi+qi*t)Nemo在0時(shí)刻的位置為(x0, y0)，它可以在海中隨意移動(dòng)，但速度不超過(guò)V。Nemo希望通過(guò)自己的努力，在T個(gè)單位時(shí)間內(nèi)(含T時(shí)刻)吃到的小蝦重量總和盡量大。當(dāng)Nemo與某只小蝦同時(shí)移動(dòng)到同一個(gè)位置上，且小蝦的重量小于Nemo當(dāng)時(shí)的重量，則Nemo可以將該小蝦吃掉。當(dāng)Nemo吃掉重量為wi的小蝦之后，它的

6、體重將增加wi。注意，小蝦不會(huì)吃Nemo，且小蝦之間也不會(huì)自相殘殺。Nemo希望你來(lái)幫助它制定一個(gè)成長(zhǎng)計(jì)劃，使得它吃掉的小蝦重量總和盡量大。特殊數(shù)據(jù)分析本題給了下面兩類特殊數(shù)據(jù)：第一類 數(shù)字金字塔：在這類數(shù)據(jù)里，蝦米都是不會(huì)移動(dòng)的。而蝦米的位置恰好排成一個(gè)金字塔形。由于時(shí)間上的限制，所以Nemo剛好能夠從上到下走一次。這樣就完全轉(zhuǎn)化成了一個(gè)數(shù)字金字塔，只需要用二維動(dòng)態(tài)規(guī)劃求出最優(yōu)解即可拿到10分。第二類 接禮物：這類數(shù)據(jù)中，蝦米都以超高的速度從上向下垂直移動(dòng)，而Nemo處于最底層。在計(jì)算中，Nemo只需要左右移動(dòng)，就能夠吃到一定數(shù)量的蝦。當(dāng)然Nemo是不可能追上蝦米的。同樣可以用動(dòng)態(tài)規(guī)劃在這樣

7、的數(shù)據(jù)上拿到810分。啟發(fā)式搜索啟發(fā)式搜索算法有很多種：蟻群算法、遺傳算法、模擬退火、禁忌搜索、爬山法、其中較常用的是模擬退火和爬山法。模擬退火的核心思想是隨機(jī)概率接受爬山法則是極大概率貪心+極小概率無(wú)條件接受模擬退火首先引入若干概念：狀態(tài)：當(dāng)前解鄰接狀態(tài)：當(dāng)前解可以通過(guò)某中方式達(dá)到的其他解評(píng)估值：狀態(tài)的價(jià)值，具體函數(shù)由題目決定，用來(lái)判斷解的優(yōu)劣具體的操作流程為：對(duì)于當(dāng)前狀態(tài)，計(jì)算出其評(píng)估值。在一定次數(shù)和范圍內(nèi)，對(duì)其鄰接狀態(tài)計(jì)算評(píng)估值，并一定概率接受某鄰接狀態(tài)為當(dāng)前狀態(tài)。持續(xù)進(jìn)行，最后達(dá)到一個(gè)較優(yōu)的解。偽代碼Pos InitializationVal Evaluate(Pos)k 0while

8、 k emax Then_Pos Neighbour(Pos)_Val Evaluate(_Pos)If Random() P(Val, _Val) ThenPos _PosVal _ValEnd Ifk k + 1End WhileReturn Pos爬山法算法流程如下：對(duì)于當(dāng)前狀態(tài)，搜索它一定數(shù)量的鄰接狀態(tài)，取出其中評(píng)估值最優(yōu)的鄰接狀態(tài)Best，若Best的評(píng)估值優(yōu)于當(dāng)前狀態(tài)，將Best作為當(dāng)前狀態(tài)；否則隨機(jī)一定的概率，接受Best作為當(dāng)前狀態(tài)。此時(shí)若仍然無(wú)法接受，當(dāng)前狀態(tài)為此次爬山的終點(diǎn)。在程序計(jì)算過(guò)程中多次從不同的起點(diǎn)進(jìn)行爬山，可以保證得到的解比較優(yōu)。由于這種算法的感覺像是不斷的在爬上

9、坡，所以稱之為爬山法。如果改變方向，也可稱之為下山法。偽代碼Pos Initializationwhile True ThenVal Evaluate(Pos)k 0BestVal 0while k BestVal ThenBest _PosBestVal _ValEnd Ifk k + 1End WhileIf BestVal Val or Random P() ThenPos BestElseBreakEnd IfEnd WhileReturn PosNOI 2008 賽程安排(match)隨著奧運(yùn)的來(lái)臨，同學(xué)們對(duì)體育的熱情日益高漲。在NOI2008來(lái)臨之際，小C和小S正策劃組織一場(chǎng)乒乓球

10、賽。小Z作為一名狂熱的乒乓球愛好者，這正是他大展身手的好機(jī)會(huì)，于是他摩拳擦掌，積極報(bào)名參賽。本次乒乓球賽采取淘汰賽制，獲勝者晉級(jí)。恰好有n (n是2的整數(shù)次冪，不妨設(shè)n = 2k)個(gè)同學(xué)報(bào)名參加，因此第一輪后就會(huì)有2k-1個(gè)同學(xué)慘遭淘汰，另外2k-1個(gè)同學(xué)晉級(jí)下一輪；第二輪后有2k-2名同學(xué)晉級(jí)下一輪， 依次類推，直到k輪后決出冠亞軍：具體的，每個(gè)人都有一個(gè)1n的初始編號(hào)，其中小Z編號(hào)為1，所有同學(xué)的編號(hào)都不同，他們將被分配到n個(gè)位置中，然后按照類似下圖的賽程進(jìn)行比賽：NOI 2008 賽程安排(match)為了吸引更多的同學(xué)參加比賽，本次比賽的獎(jiǎng)金非常豐厚。在第i輪被淘汰的選手將得到獎(jiǎng)金ai

11、元，而冠軍將獲得最高獎(jiǎng)金ak+1元。顯然獎(jiǎng)金應(yīng)滿足a1 a2 ak+1.在正式比賽前的熱身賽中，小Z連連敗北。經(jīng)過(guò)認(rèn)真分析之后，他發(fā)現(xiàn)主要的失敗原因不是他的球技問(wèn)題，而是贏他的這幾個(gè)同學(xué)在球風(fēng)上剛好對(duì)他構(gòu)成相克的關(guān)系，所以一經(jīng)交手，他自然敗陣。小Z思索：如果在正式比賽中能夠避開這幾位同學(xué)，該有多好啊!由于有著良好的人緣，小Z掌握了選手兩兩之間交手的勝率，即選手A戰(zhàn)勝選手B的概率為PA,B (保證PA,B + PB,A=1)。而小Z的伙伴小C和小S作為球賽的組織者，將負(fù)責(zé)賽程的安排。于是小Z希望能夠通過(guò)他們的幫助來(lái)確定比賽的對(duì)陣形勢(shì)（重新給每個(gè)選手進(jìn)行編號(hào)），從而能夠使得他獲得盡可能多的獎(jiǎng)金。你

12、能幫助小Z安排一個(gè)方案，使得他這場(chǎng)比賽期望獲得的獎(jiǎng)金最高么？分析首先此題的狀態(tài)很明顯是一個(gè)全排列，要求是第一位是1，那么枚舉所有情況的時(shí)間復(fù)雜度為O(N-1)!)。對(duì)于數(shù)據(jù)范圍在20以上的測(cè)試點(diǎn)已然無(wú)法在短時(shí)間內(nèi)解出，所以我們采用爬上法來(lái)解決。定義一個(gè)排列為當(dāng)前狀態(tài)，隨機(jī)交換其中任意兩個(gè)數(shù)字的位置作為鄰接狀態(tài)。設(shè)定好枚舉次數(shù)，評(píng)估值為當(dāng)前全排列能夠拿到的獎(jiǎng)金。這樣就算是把爬山法的模型套上了，接下來(lái)只需要不斷的運(yùn)行程序，調(diào)整爬山次數(shù)和尋找鄰接狀態(tài)的次數(shù)(kmax)即可。在NOI前我們用了一整天的時(shí)間來(lái)跑此題，最后基本上都拿到了7090分。賽場(chǎng)上估計(jì)能夠拿到70分左右，當(dāng)然這題也有特殊數(shù)據(jù)，正式比賽上最高分是tan