信息學(xué)競(jìng)賽——騙分導(dǎo)論

1、騙分導(dǎo)論關(guān)于應(yīng)付競(jìng)賽不會(huì)難題的策略大牛是稀有的，每道題都會(huì)的大牛更少。相信想我這樣的人還是挺多的，那競(jìng)賽時(shí)遇到不會(huì)的難題怎么辦呢？放棄？讓100 分就這樣流去？當(dāng)然不能放棄?！?】遇到難題時(shí)心態(tài)要穩(wěn)定，先搞定簡(jiǎn)單的題目，最后思考難題。心態(tài)是第一位?！?】如果難題實(shí)在不能解決也不能放棄，雖然寫(xiě)不出完美的算法，但可以用象貪心，搜索之類的算法，雖然不能Ac 但一般能過(guò)幾個(gè)，有分總比沒(méi)分好。舉個(gè)例子穿越磁場(chǎng)（cross）探險(xiǎn)機(jī)器人在Samuel 星球上尋找一塊奇特的礦石，然而此時(shí)它陷入了一片神秘的磁場(chǎng)區(qū)域，動(dòng)彈不得。探險(xiǎn)空間站立刻掃描了這片區(qū)域，繪制出該區(qū)域的磁場(chǎng)分布平面圖。這片區(qū)域中分布了N 個(gè)磁場(chǎng)

2、，每個(gè)磁場(chǎng)呈正方形，且邊與坐標(biāo)軸平行。例如下圖中，存在3 個(gè)磁場(chǎng)，白點(diǎn)表示機(jī)器人的位置，黑點(diǎn)表示礦石的位置：科學(xué)家們分析平面圖，進(jìn)一步發(fā)現(xiàn)：這些磁場(chǎng)為大小不一的正方形，可能相交，甚至覆蓋，但是它們的邊緣不會(huì)重合，頂點(diǎn)也不會(huì)重合。例如下面的兩種情形是不會(huì)出現(xiàn)的：科學(xué)家們給探險(xiǎn)機(jī)器人啟動(dòng)了磁力罩，這樣它就可以在磁場(chǎng)中自由穿越了。初始時(shí)，探險(xiǎn)機(jī)器人和所有礦石都不在任何磁場(chǎng)的邊緣。由于技術(shù)限制，XYO在穿越過(guò)程中機(jī)器人只能夠水平或垂直移動(dòng)，且不能夠沿著磁場(chǎng)的邊緣行動(dòng)。由于磁力罩的能量有限，科學(xué)家們希望探險(xiǎn)機(jī)器人穿越盡量少的磁場(chǎng)邊緣采集到這塊礦石。例如上圖中，探險(xiǎn)機(jī)器人最少需要穿越兩次磁場(chǎng)邊緣?，F(xiàn)在小聯(lián)

3、請(qǐng)你編寫(xiě)程序，幫助科學(xué)家們?cè)O(shè)計(jì)探險(xiǎn)機(jī)器人的路線，統(tǒng)計(jì)探險(xiǎn)機(jī)器人最少需要穿越多少次磁場(chǎng)邊緣。輸入（cROSS.IN）：第一行有一個(gè)整數(shù)N，表示有N 個(gè)磁場(chǎng)（1 N 100）。隨后有N 行，每行有三個(gè)整數(shù)X、Y、C（0 X ,Y ,c 10000），表示一個(gè)磁場(chǎng)左下角坐標(biāo)為（X,Y），邊長(zhǎng)為c。接下來(lái)有一行，共有四個(gè)整數(shù)SX, SY, TX,TY，表示機(jī)器人初始坐標(biāo)為（SX, SY），礦石坐標(biāo)為（TX，TY）（其中，0 S X,SY, TX, TY 10000）。輸出（cROSS.OUT）：?jiǎn)涡休敵鲆粋€(gè)整數(shù)，表示機(jī)器人最少需要穿越多少次磁場(chǎng)邊緣。樣例：輸入：213 32 1 40 0 3 4輸出：

4、2當(dāng)時(shí)我做這道題時(shí)很茫然，一點(diǎn)思路都沒(méi)有。但我認(rèn)為如果機(jī)器人和礦一個(gè)在磁場(chǎng)外面，一個(gè)在里面就一定要穿越一次。如果都在里面或外面那就不穿越。但有特殊情況，雖然想到了，但無(wú)法處理，所以我就用我錯(cuò)誤的想法編了一個(gè)。特殊情況：如果時(shí)這樣用我的算法算出來(lái)就是0，但實(shí)際上是2。我的程序主要代碼如下for i:=1 to n doif (sxmapi,1)and (symapi,2)xor (txmapi,1) and (tymapi,2)then inc(total)很短，但數(shù)據(jù)太弱了，沒(méi)有一個(gè)有如上可能。所以我全過(guò)了這樣是很劃算的，如果當(dāng)時(shí)放棄就一分都沒(méi)有了。附標(biāo)準(zhǔn)算法（2006 全國(guó)冬令營(yíng)汪曄）：（有

5、點(diǎn)復(fù)雜，當(dāng)時(shí)我絕對(duì)想不出來(lái)。） 問(wèn)題分析：方法1：將坐標(biāo)中的所有整點(diǎn)坐標(biāo)當(dāng)作頂點(diǎn)，在每個(gè)點(diǎn)與坐標(biāo)系中相鄰的點(diǎn)間加一條無(wú)向邊，如果穿過(guò)磁場(chǎng)，邊的權(quán)值為1，否則權(quán)值為0。求機(jī)器人從起點(diǎn)到終點(diǎn)的最小耗費(fèi)，也就是求構(gòu)造的圖中兩點(diǎn)之間的最短路徑，我們可以用Dijkstra 解決。每次循環(huán)中尋找最大值的復(fù)雜度為O(V)，改進(jìn)相鄰點(diǎn)時(shí)由于要判斷是否穿過(guò)磁場(chǎng)邊，所以復(fù)雜度為O(N)。整個(gè)算法復(fù)雜度為就是O(VN+V2)，這里V=整個(gè)坐標(biāo)中的點(diǎn)的個(gè)數(shù)=10000*10000，顯然超時(shí)。當(dāng)然，在實(shí)現(xiàn)過(guò)程中我們可以有所優(yōu)化，比如確定查找點(diǎn)的范圍。 方法2：Dijkstra 分為兩大部分，第一部分是取所有未標(biāo)記點(diǎn)中的

6、最小值，第二部分是用當(dāng)前最小值改進(jìn)整個(gè)圖。那么建立一個(gè)上小下大的堆，堆中保存所有起始點(diǎn)到圖中未標(biāo)記的點(diǎn)的最0 0 01 0 10 0 01 0 1000101101000O xy0 00 0 001 1101 1 11 100000 0 0 0 000 0 0 00101 12 2短路徑值，這樣每次取出一個(gè)最小值的復(fù)雜度為O(1)；由于此圖中，每個(gè)點(diǎn)的度最多為4，查找邊的權(quán)值的復(fù)雜度為O(N)，更新堆的復(fù)雜度為O(Vlog2V)。因而算法復(fù)雜度降為O(V+NV+Vlog2V)。但由于V=10000*10000 仍不能在時(shí)限中出解。方法3：此題的數(shù)據(jù)規(guī)模有一些特性雖然坐標(biāo)系的范圍巨大，但有效坐標(biāo)

7、（機(jī)器人的坐標(biāo)，寶藏的坐標(biāo)和磁場(chǎng)頂點(diǎn)坐標(biāo)）的個(gè)數(shù)卻很小。上兩個(gè)方法的主要復(fù)雜度都取決于V，也就是坐標(biāo)系中的點(diǎn)數(shù)。如果我們可以把坐標(biāo)系的范圍縮小，也就相當(dāng)于把V 縮小，就可以大大降低問(wèn)題的時(shí)間復(fù)雜度。在上種方法的構(gòu)圖中，我們會(huì)發(fā)現(xiàn)很多邊的權(quán)值為0，也就是說(shuō)，可能有很多連續(xù)點(diǎn)的最短路徑值都相等。如圖：那么我們將整個(gè)圖中有效坐標(biāo)抽出，建立一個(gè)新的坐標(biāo)系，這個(gè)坐標(biāo)系中相鄰兩個(gè)個(gè)坐標(biāo)的間距為單位“1”，但此時(shí)單位長(zhǎng)度的意義為有效坐標(biāo)的序號(hào)。如圖：這樣我們依然用最短路徑的方法在這個(gè)圖中進(jìn)行操作， 算法復(fù)雜度為O(V+VN+Vlog2V)，但此時(shí)，V=204*204，問(wèn)題得以解決。方法4：離散化后對(duì)整個(gè)圖中

8、的連續(xù)無(wú)磁場(chǎng)部分進(jìn)行染色，如下圖：?jiǎn)栴}就是求機(jī)器人所在點(diǎn)的顏色區(qū)域到寶藏所在點(diǎn)的顏色區(qū)域的最短路徑。由于每相鄰兩個(gè)區(qū)域間的邊的權(quán)值均為1，所以算法復(fù)雜度為O(V)。因而整個(gè)算法的復(fù)雜度為O(NV)。這里的N=100,V=204*204。如果先構(gòu)圖，復(fù)雜度為O(N )，再染色用寬搜求最短路復(fù)雜度為O(V)，V 所以總復(fù)雜O xy0 00 0 000 0000 0 00 000000 0 0 0 000 0 0 00000 0 00 0 0度為O(N +V V)?！?】如果太難了，連一點(diǎn)思路都沒(méi)有可以考慮只輸出一個(gè)值，如果對(duì)了也有10 分。但這個(gè)值也不能亂輸出，也要有一定的依據(jù)，輸樣例的成功率太小

9、了（nOIp2004 除外）如果題目要求誤解輸出No之類的，輸出這個(gè)肯定有分。如nOIp2005 第三題，輸出1有10 分。千萬(wàn)不要小看這10 分，當(dāng)時(shí)一等才130，很多人120郁悶了吧要輸出可能性最大的，騙要騙得精彩。如果天上能掉下來(lái)餡兒餅，那我就不用再學(xué)習(xí)了，天上能掉餡兒餅么？不能，所以我還得學(xué)習(xí)；如果天上能掉下來(lái)林妹妹，那我就不愁女友了，天上能掉林妹妹么？不能，所以我還得愁女友；如果天上能掉恐龍，那我就要時(shí)刻做好逃命的準(zhǔn)備，天上能掉恐龍么？不能，所以我不用時(shí)刻做好逃命的準(zhǔn)備；如果cheat 能過(guò)很多數(shù)據(jù)是一種錯(cuò)，那我寧愿一錯(cuò)再錯(cuò)，cheat 能過(guò)很多數(shù)據(jù)么？可以，所以，是的，我寧愿一錯(cuò)再

10、錯(cuò)重建道路(roads)【問(wèn)題描述】一場(chǎng)可怕的地震后，人們用N 個(gè)牲口棚(1N150編號(hào)1.N)重建了農(nóng)夫John 的牧場(chǎng)。由于人們沒(méi)有時(shí)間建設(shè)多余的道路，所以現(xiàn)在從一個(gè)牲口棚到另一個(gè)牲口棚的道路是惟一的。因此，牧場(chǎng)運(yùn)輸系統(tǒng)可以被構(gòu)建成一棵樹(shù)，John 想要知道另一次地震會(huì)造成多嚴(yán)重的破壞。有些道路一旦被毀壞，就會(huì)使一棵含有P(1PN)個(gè)牲口棚的子樹(shù)和剩余的牲口棚分離，John 想知道這些道路的最小數(shù)目。【輸入】第1 行：2 個(gè)整數(shù)，N 和P第2N 行：每行2 個(gè)整數(shù)I 和J，表示節(jié)點(diǎn)I 是節(jié)點(diǎn)J 的父節(jié)。【輸出】單獨(dú)一行，包含一旦被破壞將分離出恰含P 個(gè)節(jié)點(diǎn)的子樹(shù)的道路的最小數(shù)目?！緲永敵?/p>

11、】11 6 2l 2l 3l 41 52 62 72 84 94 104 11【樣例解釋】如果道路14 和15 被破壞，含有節(jié)點(diǎn)(12，3，6，7，8)的子樹(shù)將被分離出來(lái)。這道題也不是什么難題，但當(dāng)時(shí)我就不知道怎么做。我用了垃圾的搜索，效率很低很低。為了檢測(cè)我寫(xiě)的搜索是否正確，我隨機(jī)生成了很多小數(shù)據(jù)（大的嚴(yán)重超時(shí)），一測(cè)發(fā)現(xiàn)結(jié)果怎么這么多2？難道2 的機(jī)率這么大？不管這么多了，反正我也想輸樣例了（樣例也是2），于是心一恨寫(xiě)下了如下代碼writeln(2)吃驚的是我的成績(jī)，80 分?。〝?shù)據(jù)太弱了）附標(biāo)準(zhǔn)算法：用樹(shù)型動(dòng)態(tài)規(guī)劃求解。定義f(n, m)為在n 為根的子樹(shù)中取m 個(gè)節(jié)點(diǎn)的最小代價(jià)，則狀態(tài)

12、轉(zhuǎn)移方程為：f(n, m)=minf(n0, m0)+f(n1, m1)+f(n2, m2)+f(nk, mk)其中，n0, n1, n2, , nk 為n 的k 個(gè)兒子，m0+m1+m2+mk=m，并且定義f(ni, 0)=1。最后的結(jié)果為：minf(root, p), minf(n, p) | nroot看來(lái)writeln(2)的性價(jià)比還是挺高的【4】簡(jiǎn)單數(shù)學(xué)分析猜測(cè)座位的爭(zhēng)執(zhí)描述Description文件名complain.pas;還記得Matrix67 的“非常男女”計(jì)劃嗎？由Matrix67 策劃的學(xué)校大型男女配對(duì)活動(dòng)將在大禮堂隆重舉行，學(xué)校里許多人即將前來(lái)捧場(chǎng)。大禮堂一共有n 個(gè)座

13、位，為了方便管理，Matrix67 對(duì)它們從1 到n 順序編號(hào)。售票工作已經(jīng)完成，經(jīng)統(tǒng)計(jì)，共有k 個(gè)人拿到了入場(chǎng)券。由于kn，因此大禮堂的座位完全足夠。每張入場(chǎng)券上都印有座位號(hào)，入場(chǎng)者憑入場(chǎng)券對(duì)號(hào)入座。在這k 個(gè)人即將陸續(xù)入場(chǎng)時(shí)，Matrix67 發(fā)現(xiàn)了一個(gè)嚴(yán)重的錯(cuò)誤：由于在入場(chǎng)券的銷售過(guò)程中搞錯(cuò)了大禮堂總的座位數(shù)，入場(chǎng)券上印的座位號(hào)只有1 到t。雖然這t 個(gè)座位號(hào)中的每一個(gè)都在入場(chǎng)券中至少出現(xiàn)了一次，但有一個(gè)事實(shí)不能改變：tkt。第二行有k 個(gè)用空格隔開(kāi)的正整數(shù)。這些正整數(shù)保證不超過(guò)t，且所有不超過(guò)t 的種類數(shù)。第二行包含n 個(gè)整數(shù)，用空格分隔，第i 個(gè)整數(shù)ai（1 = ai = 20000

14、）是第i 種果子的數(shù)目。【輸出文件】輸出文件fruit.out 包括一行，這一行只包含一個(gè)整數(shù)，也就是最小的體力耗費(fèi)值。輸入數(shù)據(jù)保證這個(gè)值小于231?！緲永斎搿?1 2 9【樣例輸出】15【數(shù)據(jù)規(guī)?！繉?duì)于30%的數(shù)據(jù)，保證有n = 1000；對(duì)于50%的數(shù)據(jù)，保證有n = 5000；對(duì)于全部的數(shù)據(jù)，保證有n = 10000。分析：這道題數(shù)據(jù)規(guī)模太大，不好cheat，所以直接輸出樣例。得10 分。3、合唱隊(duì)形（nOIp2004_p3）pp)【問(wèn)題描述】N 位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的(NK)位同學(xué)出列，使得剩下的K 位同學(xué)排成合唱隊(duì)形。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K 位同學(xué)從左到右依次

15、編號(hào)為1, 2, , K，他們的身高分別為T(mén)1, T2, , TK，則他們的身高滿足T1 T2 Ti+1 TK (1 = i = K)。你的任務(wù)是，已知所有N 位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。【輸入文件】輸入文件chorus.in 的第一行是一個(gè)整數(shù)N（2 = N = 100），表示同學(xué)的總數(shù)。第一行有n 個(gè)整數(shù)，用空格分隔，第i 個(gè)整數(shù)Ti（130 = Ti = 230）是第i 位同學(xué)的身高（厘米）。【輸出文件】輸出文件chorus.out 包括一行，這一行只包含一個(gè)整數(shù)，就是最少需要幾位同學(xué)出列。【樣例輸入】8186 186 150 200 160

16、130 197 220【樣例輸出】4【數(shù)據(jù)規(guī)?！繉?duì)于50%的數(shù)據(jù)，保證有n = 20；對(duì)于全部的數(shù)據(jù)，保證有n = 100。分析：對(duì)于dp 還沒(méi)有入門(mén)得同學(xué)對(duì)這道題可以采用分析特殊數(shù)據(jù)樣例法if (n=8) and (a7=197) then writeln (4)else beginfor i:=1 to n1do beginif k and (anan+1) then continueelse l:=falseif (not k) and (not l) breakendif k or l then writeln (0)else writeln (n div 2)end得30 分4、蟲(chóng)食

17、算（nOIp2004p4）(alpha.pas/c/cpp)【問(wèn)題描述】所謂蟲(chóng)食算，就是原先的算式中有一部分被蟲(chóng)子啃掉了，需要我們根據(jù)剩下的數(shù)字來(lái)判定被啃掉的字母。來(lái)看一個(gè)簡(jiǎn)單的例子：43#98650#45+ 8468#663344445506978其中#號(hào)代表被蟲(chóng)子啃掉的數(shù)字。根據(jù)算式，我們很容易判斷：第一行的兩個(gè)數(shù)字分別是5 和3，第二行的數(shù)字是5?，F(xiàn)在，我們對(duì)問(wèn)題做兩個(gè)限制：首先，我們只考慮加法的蟲(chóng)食算。這里的加法是N 進(jìn)制加法，算式中三個(gè)數(shù)都有N 位，允許有前導(dǎo)的0。其次，蟲(chóng)子把所有的數(shù)都啃光了，我們只知道哪些數(shù)字是相同的。我們將相同的數(shù)字用相同的字母表示，不同的數(shù)字用不同的字母表示。

18、如果這個(gè)算式是N 進(jìn)制的，我們就取英文字母表中的前N 個(gè)大寫(xiě)字母來(lái)表示這個(gè)算式中的0 到N1這N 個(gè)不同的數(shù)字（但是這N個(gè)字母并不一定順序地代表0 到N1）。輸入數(shù)據(jù)保證N 個(gè)字母分別至少出現(xiàn)一次。BADc+ cBDADCCc上面的算式是一個(gè)4 進(jìn)制的算式。很顯然，我們只要讓ABcD 分別代表0123，便可以讓這個(gè)式子成立了。你的任務(wù)是，對(duì)于給定的N 進(jìn)制加法算式，求出N 個(gè)不同的字母分別代表的數(shù)字，使得該加法算式成立。輸入數(shù)據(jù)保證有且僅有一組解。【輸入文件】輸入文件alpha.in 包含4 行。第一行有一個(gè)正整數(shù)N（N = 26），后面的3 行每行有一個(gè)由大寫(xiě)字母組成的字符串，分別代表兩個(gè)加

19、數(shù)以及和。這3 個(gè)字符串左右兩端都沒(méi)有空格，從高位到低位，并且恰好有N 位。【輸出文件】輸出文件alpha.out 包含一行。在這一行中，應(yīng)當(dāng)包含唯一的那組解。解是這樣表示的：輸出N 個(gè)數(shù)字，分別表示A，B，c所代表的數(shù)字，相鄰的兩個(gè)數(shù)字用一個(gè)空格隔開(kāi)，不能有多余的空格?！緲永斎搿?ABcEDBDAcEEBBAA【樣例輸出】1 0 3 4 2【數(shù)據(jù)規(guī)模】對(duì)于30%的數(shù)據(jù)，保證有N = 10；對(duì)于50%的數(shù)據(jù)，保證有N = 15；對(duì)于全部的數(shù)據(jù)，保證有N =money) thenbegink:=ibreakendend然后排序一次輸出Procedure Printvar t:qwordbegi

20、nwriteln(k)t:=0for i:=1 to k1dobeginp:=finc(t,f)endpk:=moneytsortfor i:=1 to k dowrite(p,)close(output)end這樣做簡(jiǎn)單，快捷，方便。最終由于數(shù)據(jù)弱得了80 分。6、切割矩形(incise.pas)題目描述把一個(gè)a*b 矩形切割成盡量少的正方形。每次可以選擇一個(gè)矩形，沿著水平或者垂直線把它切成兩部分（不能轉(zhuǎn)彎）。兩個(gè)整數(shù)a, b(1=a,b=100)最少的正方形個(gè)數(shù)樣例輸入5 6樣例輸出5分析：一看就是dp，可是當(dāng)時(shí)我怎么也沒(méi)有想出來(lái)，于是用貪心做。每次在較長(zhǎng)邊上切去次長(zhǎng)邊。雖然這樣連樣例都過(guò)

21、不了。但還是得30 分。6、費(fèi)解的開(kāi)關(guān)（Matrix67 第一次模擬賽系列）描述Description你玩過(guò)“拉燈”游戲嗎？25 盞燈排成一個(gè)5x5 的方形。每一個(gè)燈都有一個(gè)開(kāi)關(guān)，游戲者可以改變它的狀態(tài)。每一步，游戲者可以改變某一個(gè)燈的狀態(tài)。游戲者改變一個(gè)燈的狀態(tài)會(huì)產(chǎn)生連鎖反應(yīng)：和這個(gè)燈上下左右相鄰的燈也要相應(yīng)地改變其狀態(tài)。我們用數(shù)字“1”表示一盞開(kāi)著的燈，用數(shù)字“0”表示關(guān)著的燈。下面這種狀態(tài)1011101101101111000011011在改變了最左上角的燈的狀態(tài)后將變成：0111111101101111000011011再改變它正中間的燈后狀態(tài)將變成：0111111001110011010011011給定一些游戲的初始狀態(tài)，編寫(xiě)程序判斷游戲者是否可能在6 步以內(nèi)使所有的燈都變亮。輸入格式Input Format第一行有一個(gè)正整數(shù)n，代表數(shù)據(jù)中共有n 個(gè)待解決的游戲初始狀態(tài)。以下若干行數(shù)據(jù)分為n 組，每組數(shù)據(jù)有5 行，每行5 個(gè)字符。每組數(shù)據(jù)描述了一個(gè)游戲的初始狀態(tài)。各組數(shù)據(jù)間用一個(gè)空