NOIP2010普及組復(fù)賽試題

1、全國信息學(xué)奧林匹克聯(lián)賽（NOIP2010）復(fù)賽普及組（請選手務(wù)必仔細(xì)閱讀本頁內(nèi)容）一.題目概覽中文題目名稱數(shù)字統(tǒng)計(jì) 接水問題導(dǎo)彈攔截三國游戲英文題目名稱twowatermissilesanguo可執(zhí)行文件名twowatermissilesanguo輸入文件名two.inwater.inmissile.insanguo.in輸出文件名two.outwater.outmissile.outsanguo.out每個(gè)測試點(diǎn)時(shí)限1秒1秒1秒1秒測試點(diǎn)數(shù)目10101010每個(gè)測試點(diǎn)分值10101010比較方式全文比較（過濾行末空格及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)傳統(tǒng)二.提交源程序文件名對于pascal語言

2、two.paswater.pasmissile.passanguo.pas對于C語言two.cwater.cmissilel.csanguo.c對于C+語言two.cppwater.cppmissile.cppsanguo.cpp三.編譯命令（不包含任何優(yōu)化開關(guān)）對于pascal語言fpc two.pasfpc water.pasfpc missile.pasfpc sanguo.pas對于C語言gcc o twoTwo.c -lmgcc o waterwater.c -lmgcc o missileball.c -lmgcc o sanguosanguo.c -lm對于C+語言g+ o tw

3、o two.cpp -lmg+ o seatwater.cpp -lmg+ o missilemissile.cpp -lmg+ o sanguosanguo.cpp -lm四.運(yùn)行內(nèi)存限制運(yùn)行內(nèi)存上限128M128M128M128M注意事項(xiàng)：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。 2、C/C+中函數(shù) main()的返回值類型必須是 int，程序正常結(jié)束時(shí)的返回值必須是 0。 3、全國統(tǒng)一評測時(shí)采用的機(jī)器配置為：CPU P4 3.0GHz，內(nèi)存 1G，上述時(shí)限以此配置為準(zhǔn)。各省在自測時(shí)可根據(jù)具體配置調(diào)整時(shí)限。 1數(shù)字統(tǒng)計(jì) (two.pas/c/cpp) 【問題描述】請統(tǒng)計(jì)某個(gè)給

4、定范圍L, R的所有整數(shù)中，數(shù)字 2 出現(xiàn)的次數(shù)。 比如給定范圍2, 22，數(shù)字 2 在數(shù)2中出現(xiàn)了 1次，在數(shù) 12中出現(xiàn) 1 次，在數(shù) 20 中出現(xiàn) 1 次，在數(shù) 21 中出現(xiàn) 1 次，在數(shù) 22 中出現(xiàn) 2 次，所以數(shù)字 2 在該范圍內(nèi)一共出現(xiàn)了 6次?！据斎搿枯斎胛募麨?two.in。 輸入共 1 行，為兩個(gè)正整數(shù) L 和 R，之間用一個(gè)空格隔開?！据敵觥枯敵鑫募麨?two.out。 輸出共 1 行，表示數(shù)字 2 出現(xiàn)的次數(shù)?！据斎胼敵鰳永?】wo.out2 226【輸入輸出樣例2】wo.out2 10020【數(shù)據(jù)范圍】 1 L R 10000。 2.

5、接水問題(water.pas/c/cpp)【問題描述】學(xué)校里有一個(gè)水房，水房里一共裝有 m 個(gè)龍頭可供同學(xué)們打開水，每個(gè)龍頭每秒鐘的供水量相等，均為 1。 現(xiàn)在有 n 名同學(xué)準(zhǔn)備接水，他們的初始接水順序已經(jīng)確定。將這些同學(xué)按接水順序從 1到 n 編號，i號同學(xué)的接水量為 wi。接水開始時(shí)，1 到 m號同學(xué)各占一個(gè)水龍頭，并同時(shí)打開水龍頭接水。當(dāng)其中某名同學(xué) j 完成其接水量要求 wj 后，下一名排隊(duì)等候接水的同學(xué) k馬上接替 j 同學(xué)的位置開始接水。這個(gè)換人的過程是瞬間完成的，且沒有任何水的浪費(fèi)。即j 同學(xué)第x 秒結(jié)束時(shí)完成接水， 則 k 同學(xué)第 x+1 秒立刻開始接水。 若當(dāng)前接水人數(shù) n不

6、足 m，則只有 n個(gè)龍頭供水，其它 mn個(gè)龍頭關(guān)閉。 現(xiàn)在給出 n名同學(xué)的接水量，按照上述接水規(guī)則，問所有同學(xué)都接完水需要多少秒?！据斎搿枯斎胛募麨?water.in。 第 1 行2 個(gè)整數(shù) n 和 m，用一個(gè)空格隔開，分別表示接水人數(shù)和龍頭個(gè)數(shù)。 第 2 行 n 個(gè)整數(shù) w1、w2、wn，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，wi表示 i 號同學(xué)的接水量?！据敵觥枯敵鑫募麨?water.out。 輸出只有一行，1 個(gè)整數(shù)，表示接水所需的總時(shí)間?！据斎胼敵鰳永?】water.inwater.out5 3 4 4 1 2 14【輸入輸出樣例1解釋】 第 1 秒，3 人接水。第 1秒結(jié)束時(shí)，1、2、3

7、 號同學(xué)每人的已接水量為 1，3 號同學(xué)接完水，4 號同學(xué)接替 3 號同學(xué)開始接水。 第 2 秒，3 人接水。第 2 秒結(jié)束時(shí)，1、2 號同學(xué)每人的已接水量為 2，4 號同學(xué)的已接水量為 1。 第 3 秒，3 人接水。第 3 秒結(jié)束時(shí)，1、2 號同學(xué)每人的已接水量為 3，4 號同學(xué)的已接水量為 2。4號同學(xué)接完水，5 號同學(xué)接替 4 號同學(xué)開始接水。 第 4 秒，3 人接水。第 4 秒結(jié)束時(shí)，1、2 號同學(xué)每人的已接水量為 4，5 號同學(xué)的已接水量為 1。1、2、5 號同學(xué)接完水，即所有人完成接水。 總接水時(shí)間為 4 秒?！据斎胼敵鰳永?】water.inwater.out8 4 23 71

8、87 32 70 93 80 76163【數(shù)據(jù)范圍】 1 n 10000，1 m 100 且 m n； 1 wi 100。 3 導(dǎo)彈攔截 (missile.pas/c/cpp)【問題描述】經(jīng)過 11 年的韜光養(yǎng)晦，某國研發(fā)出了一種新的導(dǎo)彈攔截系統(tǒng)，凡是與它的距離不超過其工作半徑的導(dǎo)彈都能夠被它成功攔截。當(dāng)工作半徑為 0 時(shí)，則能夠攔截與它位置恰好相同的導(dǎo)彈。但該導(dǎo)彈攔截系統(tǒng)也存在這樣的缺陷：每套系統(tǒng)每天只能設(shè)定一次工作半徑。而當(dāng)天的使用代價(jià)，就是所有系統(tǒng)工作半徑的平方和。 某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)尚處于試驗(yàn)階段，所以只有兩套系統(tǒng)投入工作。如果現(xiàn)在的要求是攔截所有的導(dǎo)彈，請計(jì)算

9、這一天的最小使用代價(jià)?！据斎搿枯斎胛募?missile.in。 第一行包含 4 個(gè)整數(shù)x1、y1、x2、y2，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，表示這兩套導(dǎo)彈攔截系統(tǒng)的坐標(biāo)分別為(x1, y1)、(x2, y2)。 第二行包含 1 個(gè)整數(shù) N，表示有 N顆導(dǎo)彈。接下來 N行，每行兩個(gè)整數(shù) x、y，中間用一個(gè)空格隔開，表示一顆導(dǎo)彈的坐標(biāo)(x, y)。不同導(dǎo)彈的坐標(biāo)可能相同?！据敵觥枯敵鑫募?missile.out。 輸出只有一行，包含一個(gè)整數(shù)，即當(dāng)天的最小使用代價(jià)?！咎崾尽?兩個(gè)點(diǎn)(x1, y1)、(x2, y2)之間距離的平方是(x1 x2)2+(y1y2)2。 兩套系統(tǒng)工作半徑 r1、r2的

10、平方和，是指 r1、r2 分別取平方后再求和，即 r12+r22。【輸入輸出樣例1】missile.inmissile.out0 0 10 02-3 310 018【樣例 1 說明】 樣例1中要攔截所有導(dǎo)彈，在滿足最小使用代價(jià)的前提下，兩套系統(tǒng)工作半徑的平方分別為 18 和 0?！据斎胼敵鰳永?】missile.inmissile.out0 0 6 0 5 -4 -2 -2 3 4 0 6 -2 9 130【樣例 2 說明】 樣例中的導(dǎo)彈攔截系統(tǒng)和導(dǎo)彈所在的位置如下圖所示。要攔截所有導(dǎo)彈，在滿足最小使用代價(jià)的前提下，兩套系統(tǒng)工作半徑的平方分別為 20 和 10?！緮?shù)據(jù)范圍】 對于 10%的數(shù)據(jù)

11、，N = 1 對于 20%的數(shù)據(jù)，1 N 2 對于 40%的數(shù)據(jù)，1 N 100 對于 70%的數(shù)據(jù)，1 N 1000 對于 100%的數(shù)據(jù)，1 N 100000，且所有坐標(biāo)分量的絕對值都不超過 1000。4 三國游戲 (sanguo.pas/c/cpp)【問題描述】小涵很喜歡電腦游戲，這些天他正在玩一個(gè)叫做三國的游戲。 在游戲中， 小涵和計(jì)算機(jī)各執(zhí)一方， 組建各自的軍隊(duì)進(jìn)行對戰(zhàn)。 游戲中共有 N位武將 （N為偶數(shù)且不小于 4） ，任意兩個(gè)武將之間有一個(gè)“默契值” ，表示若此兩位武將作為一對組合作戰(zhàn)時(shí)，該組合的威力有多大。游戲開始前，所有武將都是自由的（稱為自由武將，一旦某個(gè)自由武將被選中作為

12、某方軍隊(duì)的一員，那么他就不再是自由武將了） ，換句話說，所謂的自由武將不屬于任何一方。游戲開始，小涵和計(jì)算機(jī)要從自由武將中挑選武將組成自己的軍隊(duì)，規(guī)則如下：小涵先從自由武將中選出一個(gè)加入自己的軍隊(duì)，然后計(jì)算機(jī)也從自由武將中選出一個(gè)加入計(jì)算機(jī)方的軍隊(duì)。接下來一直按照“小涵計(jì)算機(jī)小涵”的順序選擇武將，直到所有的武將被雙方均分完。然后，程序自動(dòng)從雙方軍隊(duì)中各挑出一對默契值最高的武將組合代表自己的軍隊(duì)進(jìn)行二對二比武，擁有更高默契值的一對武將組合獲勝，表示兩軍交戰(zhàn)，擁有獲勝武將組合的一方獲勝。 已知計(jì)算機(jī)一方選擇武將的原則是盡量破壞對手下一步將形成的最強(qiáng)組合，它采取的具體策略如下：任何時(shí)刻，輪到計(jì)算機(jī)挑

13、選時(shí)，它會嘗試將對手軍隊(duì)中的每個(gè)武將與當(dāng)前每個(gè)自由武將進(jìn)行一一配對，找出所有配對中默契值最高的那對武將組合，并將該組合中的自由武將選入自己的軍隊(duì)。 下面舉例說明計(jì)算機(jī)的選將策略，例如，游戲中一共有 6個(gè)武將，他們相互之間的默契值如下表所示雙方選將過程如下所示： 小涵想知道，如果計(jì)算機(jī)在一局游戲中始終堅(jiān)持上面這個(gè)策略，那么自己有沒有可能必勝？如果有，在所有可能的勝利結(jié)局中，自己那對用于比武的武將組合的默契值最大是多少？ 假設(shè)整個(gè)游戲過程中，對戰(zhàn)雙方任何時(shí)候均能看到自由武將隊(duì)中的武將和對方軍隊(duì)的武將。為了簡化問題，保證對于不同的武將組合，其默契值均不相同?！据斎搿枯斎胛募麨?sanguo.in，

14、共 N行。 第一行為一個(gè)偶數(shù) N，表示武將的個(gè)數(shù)。 第 2 行到第 N 行里，第（i+1）行有（Ni）個(gè)非負(fù)整數(shù)，每兩個(gè)數(shù)之間用一個(gè)空格隔開，表示 i 號武將和 i+1，i+2，N號武將之間的默契值（0 默契值 1,000,000,000）?！据敵觥?輸出文件 sanguo.out 共 1或 2 行。 若對于給定的游戲輸入，存在可以讓小涵獲勝的選將順序，則輸出 1，并另起一行輸出所有獲勝的情況中，小涵最終選出的武將組合的最大默契值。 如果不存在可以讓小涵獲勝的選將順序，則輸出 0。【輸入輸出樣例1】sanguo.insanguo.out6 5 28 16 29 27 23 3 20 1 8 3

15、2 26 33 11 12132【輸入輸出樣例說明1】 首先小涵拿走 5 號武將；計(jì)算機(jī)發(fā)現(xiàn) 5 號武將和剩下武將中的 4 號默契值最高，于是拿走 4 號；小涵接著拿走 3 號；計(jì)算機(jī)發(fā)現(xiàn) 3、5 號武將之一和剩下的武將配對的所有組合中，5 號和1 號默契值最高，于是拿走 1號；小涵接著拿走 2 號；計(jì)算機(jī)最后拿走 6 號。在小涵手里的 2，3，5 號武將中，3 號和 5 號配合最好，默契值為 32，而計(jì)算機(jī)能推出的最好組合為 1 號和 6 號，默契值為 27。結(jié)果為小涵勝，并且這個(gè)組合是小涵用盡所有方法能取到的最好組合?！据斎胼敵鰳永?】sanguo.insanguo.out8 42 24

16、10 29 27 12 58 31 8 16 26 80 6 25 3 36 11 5 33 20 17 13 15 77 9 4 50 19 177 【數(shù)據(jù)范圍】 對于 40%的數(shù)據(jù)有 N 10。 對于 70%的數(shù)據(jù)有 N 18。 對于 100%的數(shù)據(jù)有 N 500。 var a:array1.500,1.500of longint; i,j,n,max1,max2,maxall:longint;beginassign(input,'sanguo.in'); assign(output,'sanguo.out');reset(input); rewrite(o

17、utput);readln(n); 以下這段是讀入默契值for i:=1 to n-1 do 讀入武將i和其他武將搭配的默契值 for j:=i+1 to n do 只要讀入序號在i之后的搭配默契值即可，否則會有重復(fù) begin read(ai,j); aj,i:=ai,j; 讀的是一個(gè)三角形，在讀的時(shí)候轉(zhuǎn)換成 n*n的方陣（方陣沿對角線對稱） end;maxall:=0; maxall用來存放次大值中的最大值for i:=1 to n do 枚舉武將i和其他武將搭配的情況 begin max1:=0;max2:=0; max1是武將i和其他武將搭配情況中的最大值，而max2是次大值 for j:=1 to n do 枚舉武將i和武將j搭配的情況 if j<>i then 自己不能和自己搭配 begin if ai,j>max1 then 默契值i,j比最大默契值大的情況 begin max2:=max1; 最大值和次大值依次迭代掉 max1: