答案提交題目解題方法

ByNettle答案提交題目解題方法什么是答案提交題目在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程序：某些題目中用來(lái)檢查選手輸出文件是否合法的程序NOI2004畢業(yè)生(graduate)在一個(gè)二維平面上，給定一些積木。要求將積木按照一定的方式擺放，再用一個(gè)矩形將其圍起來(lái)，目的是使矩形的面積最小。

graduate1.in

graudate2.inCheck程序的使用Windows系統(tǒng)下：在命令行cmd中，進(jìn)入存放.in和.out文件的文件夾，此時(shí)須保證check程序也在該文件夾，調(diào)用命令：check<Number>Linux系統(tǒng)下：在終端中，進(jìn)入存放.in和.out文件的文件夾，同樣須保證check程序存放在該文件夾，調(diào)用命令：./check<Number>其中<Number>表示測(cè)試數(shù)據(jù)的編號(hào)。調(diào)用命令不一定是上面兩種，需要根據(jù)題目說(shuō)明決定。但是調(diào)用時(shí)當(dāng)前目錄一定要為數(shù)據(jù)文件夾。答案提交題目常用解題方法借助圖畫(huà)、記事本等工具手算寫(xiě)搜索程序，算可行解(答案提交的題通常提交即可得1分)非完美程序，針對(duì)特殊數(shù)據(jù)寫(xiě)特殊算法啟發(fā)式搜索借助圖畫(huà)、記事本等工具手算通常情況下，所有提交答案的題目前2~3個(gè)點(diǎn)數(shù)據(jù)范圍都比較小，可以手算。比如說(shuō)剛剛看過(guò)的題目《畢業(yè)生》，此題前5個(gè)點(diǎn)均可以通過(guò)觀察數(shù)據(jù)進(jìn)行手動(dòng)驗(yàn)證，大概花上1個(gè)小時(shí)能夠拿到40~50分。在NOI考場(chǎng)上是會(huì)發(fā)放草稿紙的，不夠了應(yīng)該還是可以繼續(xù)要。所以多動(dòng)動(dòng)筆就能夠拿到一定的分?jǐn)?shù)。搜索程序搜索程序可以拿到基本分。對(duì)于某些有解即可得分的題目，可以考慮搜索算法，求出任意一個(gè)可行解，這樣可以至少保證拿到1分。如果Rp比較好，也有可能拿到5分以上。這一類的題目有：NOI2007調(diào)兵遣將NOI2006聰明的導(dǎo)游NOI2002新俄羅斯方塊非完美程序非完美程序是用處較大的一種方法。由于出題人通常都會(huì)弄至少一組特殊數(shù)據(jù)，所以我們?nèi)绻軌蚺袛喑鲞@些數(shù)據(jù)，并對(duì)其進(jìn)行分析，寫(xiě)出針對(duì)算法，此類數(shù)據(jù)點(diǎn)基本上能夠拿到8~10分，某些題目點(diǎn)甚至有可能拿到11~12分。這里以NOI2010成長(zhǎng)快樂(lè)為例來(lái)講：NOI2010成長(zhǎng)快樂(lè)(Nemo)Nemo是一條無(wú)憂無(wú)慮的小魚(yú)，它的初始體重為w0?？蓯?ài)的Nemo希望自己能夠盡快地成長(zhǎng)，因此需要吃盡量多的食物。Nemo最喜愛(ài)的食物是海里的小蝦。已知Nemo對(duì)食物的情況了解如下：大海里共有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的小蝦之后，它的體重將增加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ī)劃在這樣的數(shù)據(jù)上拿到8~10