NOIP歷年復(fù)賽提高組試題

2004?2013年NOIP復(fù)賽試題集（提高組）第十屆全國信息學(xué)奧林匹克分區(qū)聯(lián)賽（NOIP2004）復(fù)賽試題（提高組競賽用時(shí)：3小時(shí)）1、津津的儲(chǔ)蓄計(jì)劃（Save.pas/dpr/c/cpp）【問題描述】津津的零花錢一直都是自己管理。每個(gè)月的月初媽媽給津津300元錢，津津會(huì)預(yù)算這個(gè)月的花銷，并且總能做到實(shí)際花銷和預(yù)算的相同。為了讓津津?qū)W習(xí)如何儲(chǔ)蓄，媽媽提出，津津可以隨時(shí)把整百的錢存在她那里，到了年末她會(huì)加上20%還給津津。因此津津制定了一個(gè)儲(chǔ)蓄計(jì)劃：每個(gè)月的月初，在得到媽媽給的零花錢后，如果她預(yù)計(jì)到這個(gè)月的月末手中還會(huì)有多于100元或恰好100元，她就會(huì)把整百的錢存在媽媽那里，剩余的錢留在自己手中。例如11月初津津手中還有83元，媽媽給了津津300元。津津預(yù)計(jì)11月的花銷是180元，那么她就會(huì)在媽媽那里存200元，自己留下183元。到了11月月末，津津手中會(huì)剩下3元錢。津津發(fā)現(xiàn)這個(gè)儲(chǔ)蓄計(jì)劃的主要風(fēng)險(xiǎn)是，存在媽媽那里的錢在年末之前不能取出。有可能在某個(gè)月的月初，津津手中的錢加上這個(gè)月媽媽給的錢，不夠這個(gè)月的原定預(yù)算。如果出現(xiàn)這種情況，津津?qū)⒉坏貌辉谶@個(gè)月省吃儉用，壓縮預(yù)算。現(xiàn)在請(qǐng)你根據(jù)2004年1月到12月每個(gè)月津津的預(yù)算，判斷會(huì)不會(huì)出現(xiàn)這種情況。如果不會(huì)，計(jì)算到2004年年末，媽媽將津津平常存的錢加上20%還給津津之后，津津手中會(huì)有多少錢?！据斎胛募枯斎胛募ave.in包括12行數(shù)據(jù)，每行包含一個(gè)小于350的非負(fù)整數(shù)，分別表示1月到12月津津的預(yù)算?！据敵鑫募枯敵鑫募ave.out包括一行，這一行只包含一個(gè)整數(shù)。如果儲(chǔ)蓄計(jì)劃實(shí)施過程中出現(xiàn)某個(gè)月錢不夠用的情況，輸出-X,X表示出現(xiàn)這種情況的第一個(gè)月；否則輸出到2004年年末津津手中會(huì)有多少錢?！緲永斎?】29023028020030017034050908020060第1頁共73頁2004?2013年NOIP復(fù)賽試題集（提高組）【樣例輸出1】-7【樣例輸入2】29023028020030017033050908020060【樣例輸出2】1580第2頁共73頁2004?2013年NOIP復(fù)賽試題集(提高組)2、合并果子(fruit.pas/dpr/c/cpp)【問題描述】在一個(gè)果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯?，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時(shí)總共消耗的體力等于每次合并所耗體力之和。因?yàn)檫€要花大力氣把這些果子搬回家，所以多多在合并果子時(shí)要盡可能地節(jié)省體力。假定每個(gè)果子重量都為1,并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計(jì)出合并的次序方案，使多多耗費(fèi)的體力最少，并輸出這個(gè)最小的體力耗費(fèi)值。例如有3種果子，數(shù)目依次為1,2,9?？梢韵葘?、2堆合并，新堆數(shù)目為3,耗費(fèi)體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12,耗費(fèi)體力為12。所以多多總共耗費(fèi)體力=3+12=15?？梢宰C明15為最小的體力耗費(fèi)值?！据斎胛募枯斎胛募ruit.in包括兩行，第一行是一個(gè)整數(shù)n(1<=n<=10000),表示果子的種類數(shù)。第二行包含n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)ai(1<=ai<=20000)是第i種果子的數(shù)目?！据敵鑫募枯敵鑫募ruit.out包括一行，這一行只包含一個(gè)整數(shù)，也就是最小的體力耗費(fèi)值。輸入數(shù)據(jù)保證這個(gè)值小于231?！緲永斎搿?129【樣例輸出】15【數(shù)據(jù)規(guī)模】對(duì)于30%的數(shù)據(jù)，保證有n<=1000：對(duì)于50%的數(shù)據(jù)，保證有n<=5000；對(duì)于全部的數(shù)據(jù)，保證有n<=10000。2004?2013年NOIP復(fù)賽試題集(提高組)3、合唱隊(duì)形(chorus.pas/dpr/c/cpp)【問題描述】N位同學(xué)站成一排，音樂老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1,2…，K,他們的身高分別為T1,T2,…，TK,則他們的身高滿足T1<...<Ti>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é)的身高(厘米)?！据敵鑫募枯敵鑫募horus.out包括一行，這一行只包含一個(gè)整數(shù)，就是最少需要幾位同學(xué)出列?！緲永斎搿?186186150200160130197220【樣例輸出】4【數(shù)據(jù)規(guī)模】對(duì)于50%的數(shù)據(jù)，保證有n<=20；對(duì)于全部的數(shù)據(jù)，保證有n<=100。2004?2013年NOIP復(fù)賽試題集(提高組)4、蟲食算(alpha.pas/dpr/c/cpp)【問題描述】所謂蟲食算，就是原先的算式中有一部分被蟲子啃掉了，需要我們根據(jù)剩下的數(shù)字來判定被啃掉的字母。來看一個(gè)簡單的例子：43#9865#045+8468#663344445509678其中#號(hào)代表被蟲子啃掉的數(shù)字。根據(jù)算式，我們很容易判斷：第一行的兩個(gè)數(shù)字分別是5和3,第二行的數(shù)字是5。現(xiàn)在，我們對(duì)問題做兩個(gè)限制：首先，我們只考慮加法的蟲食算。這里的加法是N進(jìn)制加法，算式中三個(gè)數(shù)都有N位，允許有前導(dǎo)的0。其次，蟲子把所有的數(shù)都啃光了，我們只知道哪些數(shù)字是相同的，我們將相同的數(shù)字用相同的字母表示，不同的數(shù)字用不同的字母表示。如果這個(gè)算式是N進(jìn)制的，我們就取英文字母表午的前N個(gè)大寫字母來表示這個(gè)算式中的0到N-1這N個(gè)不同的數(shù)字：但是這N個(gè)字母并不一定順序地代表0到N-1)。輸入數(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è)由大寫字母組成的字符串，分別代表兩個(gè)加數(shù)以及和。這3個(gè)字符串左右兩端都沒有空格，從高位到低位，并且恰好有N位?！据敵鑫募枯敵鑫募lpha.out包含一行。在這一行中，應(yīng)當(dāng)包含唯一的那組解。解是這樣表示的：輸出N個(gè)數(shù)字，分別表示A，B，C……所代表的數(shù)字，相鄰的兩個(gè)數(shù)字用一個(gè)空格隔開，不能有多余的空格?！緲永斎搿?ABCEDBDACEEBBAA【樣例輸出】10342【數(shù)據(jù)規(guī)?！繉?duì)于30%的數(shù)據(jù)，保證有N<=10；對(duì)于50%的數(shù)據(jù)，保證有N<=15；對(duì)于全部的數(shù)據(jù)，保證有N<=26。2004?2013年NOIP復(fù)賽試題集（提高組）第十一屆全國信息學(xué)奧林匹克分區(qū)聯(lián)賽（NOIP2005）復(fù)賽試題（提高組競賽用時(shí)：3小時(shí)）1、誰拿了最多獎(jiǎng)學(xué)金（scholar.pas/c/cpp）【問題描述】某校的慣例是在每學(xué)期的期末考試之后發(fā)放獎(jiǎng)學(xué)金。發(fā)放的獎(jiǎng)學(xué)金共有五種，獲取的條件各自不同：1）院士獎(jiǎng)學(xué)金，每人8000元，期末平均成績高于80分（＞80），并且在本學(xué)期內(nèi)發(fā)表1篇或1篇以上論文的學(xué)生均可獲得；2）五四獎(jiǎng)學(xué)金，每人4000元，期末平均成績高于85分（＞85），并且班級(jí)評(píng)議成績高于80分（＞80）的學(xué)生均可獲得；3）成績優(yōu)秀獎(jiǎng)，每人2000元，期末平均成績高于90分（＞90）的學(xué)生均可獲得；4）西部獎(jiǎng)學(xué)金，每人1000元，期末平均成績高于85分（＞85）的西部省份學(xué)生均可獲得；5）班級(jí)貢獻(xiàn)獎(jiǎng)，每人850元，班級(jí)評(píng)議成績高于80分（＞80）的學(xué)生干部均可獲得；只要符合條件就可以得獎(jiǎng)，每項(xiàng)獎(jiǎng)學(xué)金的獲獎(jiǎng)人數(shù)沒有限制，每名學(xué)生也可以同時(shí)獲得多項(xiàng)獎(jiǎng)學(xué)金。例如姚林的期末平均成績是87分，班級(jí)評(píng)議成績82分，同時(shí)他還是一位學(xué)生干部，那么他可以同時(shí)獲得五四獎(jiǎng)學(xué)金和班級(jí)貢獻(xiàn)獎(jiǎng)，獎(jiǎng)金總數(shù)是4850元。現(xiàn)在給出若干學(xué)生的相關(guān)數(shù)據(jù)，請(qǐng)計(jì)算哪些同學(xué)獲得的獎(jiǎng)金總數(shù)最高（假設(shè)總有同學(xué)能滿足獲得獎(jiǎng)學(xué)金的條件）?！据斎胛募枯斎胛募cholar.in的第一行是一個(gè)整數(shù)N（1＜=N＜=100），表示學(xué)生的總數(shù)。接下來的N行每行是一位學(xué)生的數(shù)據(jù)，從左向右依次是姓名，期末平均成績，班級(jí)評(píng)議成績，是否是學(xué)生干部，是否是西部省份學(xué)生，以及發(fā)表的論文數(shù)。姓名是由大小寫英文字母組成的長度不超過20的字符串（不含空格）；期末平均成績和班級(jí)評(píng)議成績都是0到100之間的整數(shù)（包括0和100）；是否是學(xué)生干部和是否是西部省份學(xué)生分別用一個(gè)字符表示，丫表示是，N表示不是；發(fā)表的論文數(shù)是0到10的整數(shù)（包括0和10）。每兩個(gè)相鄰數(shù)據(jù)項(xiàng)之間用一個(gè)空格分隔?！据敵鑫募枯敵鑫募cholar.out包括三行，第一行是獲得最多獎(jiǎng)金的學(xué)生的姓名，第二行是這名學(xué)生獲得的獎(jiǎng)金總數(shù)。如果有兩位或兩位以上的學(xué)生獲得的獎(jiǎng)金最多，輸出他們之中在輸入文件中出現(xiàn)最早的學(xué)生的姓名。第三行是這N個(gè)學(xué)生獲得的獎(jiǎng)學(xué)金的總數(shù)。【樣例輸入】4YaoLin8782YN0ChenRuiyi8878NY1LiXin9288NN0ZhangQin8387YN1【樣例輸出】ChenRuiyi9000287002004?2013年NOIP復(fù)賽試題集（提高組）2、過河（river.pas/c/cpp）【問題描述】在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石子，青蛙很討厭踩在這些石子上。由于橋的長度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)：0，1，……，L（其中L是橋的長度）。坐標(biāo)為0的點(diǎn)表示橋的起點(diǎn)，坐標(biāo)為L的點(diǎn)表示橋的終點(diǎn)。青蛙從橋的起點(diǎn)開始，不停的向終點(diǎn)方向跳躍。一次跳躍的距離是S到T之間的任意正整數(shù)（包括S,T）。當(dāng)青蛙跳到或跳過坐標(biāo)為L的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。題目給出獨(dú)木橋的長度L，青蛙跳躍的距離范圍S,T，橋上石子的位置。你的任務(wù)是確定青蛙要想過河，最少需要踩到的石子數(shù)。【輸入文件】輸入文件river.in的第一行有一個(gè)正整數(shù)L（1<=L<=109），表示獨(dú)木橋的長度。第二行有三個(gè)正整數(shù)S，T，M，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個(gè)數(shù)，其中1<=S<=T<=10，1<=M<=100。第三行有M個(gè)不同的正整數(shù)分別表示這M個(gè)石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒有石子）。所有相鄰的整數(shù)之間用一個(gè)空格隔開?！据敵鑫募枯敵鑫募iver.out只包括一個(gè)整數(shù)，表示青蛙過河最少需要踩到的石子數(shù)?！緲永斎搿?023523567【樣例輸出】2【數(shù)據(jù)規(guī)模】對(duì)于30%的數(shù)據(jù)，L<=10000；對(duì)于全部的數(shù)據(jù)，L<=109。2004?2013年NOIP復(fù)賽試題集(提高組)3、篝火晚會(huì)(fire,pas/c/cpp)【問題描述】佳佳剛進(jìn)高中，在軍訓(xùn)的時(shí)候，由于佳佳吃苦耐勞，很快得到了教官的賞識(shí)，成為了小教官”。在軍訓(xùn)結(jié)束的那天晚上，佳佳被命令組織同學(xué)們進(jìn)行篝火晚會(huì)。一共有n個(gè)同學(xué)，編號(hào)從1到n。一開始，同學(xué)們按照1，2,……，n的順序坐成一圈，而實(shí)際上每個(gè)人都有兩個(gè)最希望相鄰的同學(xué)。如何下命令調(diào)整同學(xué)的次序，形成新的一個(gè)圈，使之符合同學(xué)們的意愿，成為擺在佳佳面前的一大難題。佳佳可向同學(xué)們下達(dá)命令，每一個(gè)命令的形式如下：(b1，b2,…bm-1，bm)這里m的值是由佳佳決定的，每次命令m的值都可以不同。這個(gè)命令的作用是移動(dòng)編號(hào)是耳，b2,……bm-1，bm的這m個(gè)同學(xué)的位置。要求b1換到b2的位置上，b2換到b3的位置上，……，要求bm換到b1的位置上。1執(zhí)行每個(gè)命令都需要一些代價(jià)。我們假定如果一個(gè)命令要移動(dòng)m個(gè)人的位置，那么這個(gè)命令的代價(jià)就是m。我們需要佳佳用最少的總代價(jià)實(shí)現(xiàn)同學(xué)們的意愿，你能幫助佳佳嗎？【輸入文件】輸入文件fire.in的第一行是一個(gè)整數(shù)n(3<=n<=50000)，表示一共有n個(gè)同學(xué)。其后n行每行包括兩個(gè)不同的正整數(shù)，以一個(gè)空格隔開，分別表示編號(hào)是1的同學(xué)最希望相鄰的兩個(gè)同學(xué)的編號(hào)，編號(hào)是2的同學(xué)最希望相鄰的兩個(gè)同學(xué)的編號(hào)，……，編號(hào)是n的同學(xué)最希望相鄰的兩個(gè)同學(xué)的編號(hào)?！据敵鑫募枯敵鑫募ire.out包括一行，這一行只包含一個(gè)整數(shù)，為最小的總代價(jià)。如果無論怎么調(diào)整都不能符合每個(gè)同學(xué)的愿望，則輸出-1。【樣例輸入】44322【樣例輸出】【數(shù)據(jù)規(guī)?！繉?duì)于30%的數(shù)據(jù)，n<=1000；對(duì)于全部的數(shù)據(jù)，n<=50000。2004?2013年NOIP復(fù)賽試題集(提高組)4、等價(jià)表達(dá)式(equal.pas/c/cpp)【問題描述】明明進(jìn)了中學(xué)之后，學(xué)到了代數(shù)表達(dá)式。有一天，他碰到一個(gè)很麻煩的選擇題。這個(gè)題目的題干中首先給出了一個(gè)代數(shù)表達(dá)式，然后列出了若干選項(xiàng)，每個(gè)選項(xiàng)也是一個(gè)代數(shù)表達(dá)式，題目的要求是判斷選項(xiàng)中哪些代數(shù)表達(dá)式是和題干中的表達(dá)式等價(jià)的。這個(gè)題目手算很麻煩，因?yàn)槊髅鲗?duì)計(jì)算機(jī)編程很感興趣，所以他想是不是可以用計(jì)算機(jī)來解決這個(gè)問題。假設(shè)你是明明，能完成這個(gè)任務(wù)嗎？這個(gè)選擇題中的每個(gè)表達(dá)式都滿足下面的性質(zhì)：.表達(dá)式只可能包含一個(gè)變量‘a(chǎn)’。.表達(dá)式中出現(xiàn)的數(shù)都是正整數(shù)，而且都小于10000O.表達(dá)式中可以包括四種運(yùn)算'+‘(加)，‘-‘(減)，‘*’(乘)，‘八’(乘幕)，以及小括號(hào)’(‘，‘)’。小括號(hào)的優(yōu)先級(jí)最高，其次是‘八’，然后是‘*’，最后是‘+’和‘-’。'+’和‘-’的優(yōu)先級(jí)是相同的。相同優(yōu)先級(jí)的運(yùn)算從左到右進(jìn)行。(注意：運(yùn)算符‘+‘，‘-'，‘*‘，‘八’以及小括號(hào)’(‘，’)’都是英文字符).幕指數(shù)只可能是1到10之間的正整數(shù)(包括1和10)o.表達(dá)式內(nèi)部，頭部或者尾部都可能有一些多余的空格。下面是一些合理的表達(dá)式的例子：((aA1)A2)A3,a*a+a-a,((a+a)),9999+(a-a)*a,1+(a-1)A3,1A10A9……【輸入文件】輸入文件equal.in的第一行給出的是題干中的表達(dá)式。第二行是一個(gè)整數(shù)n(2<=n<=26),表示選項(xiàng)的個(gè)數(shù)。后面n行，每行包括一個(gè)選項(xiàng)中的表達(dá)式。這n個(gè)選項(xiàng)的標(biāo)號(hào)分別是A,B,C,D……輸入表達(dá)式的長度都不超過50個(gè)字符，且保證選項(xiàng)中總有表達(dá)式和題干中的表達(dá)式是等價(jià)的?！据敵鑫募枯敵鑫募qual.out包括一行，這一行包括一系列選項(xiàng)的標(biāo)號(hào)，表示哪些選項(xiàng)是和題干中的表達(dá)式等價(jià)的。選項(xiàng)的標(biāo)號(hào)按照字母順序排列，而且之間沒有空格?！緲永斎搿?a+1)A23(a-1)A2+4*aa+1+aaA2+2*a*1+?2+10-10+a-a【樣例輸出】AC【數(shù)據(jù)規(guī)模】對(duì)于30%的數(shù)據(jù)，表達(dá)式中只可能出現(xiàn)兩種運(yùn)算符‘+‘和‘-’；對(duì)于其它的數(shù)據(jù)，四種運(yùn)算符‘+‘，‘-'，‘*‘，'八’在表達(dá)式中都可能出現(xiàn)。對(duì)于全部的數(shù)據(jù)，表達(dá)式中都可能出現(xiàn)小括號(hào)’('和‘)’。2004?2013年NOIP復(fù)賽試題集（提高組）第十二屆全國信息學(xué)奧林匹克分區(qū)聯(lián)賽（NOIP2006）復(fù)賽試題（提高組競賽用時(shí)：3小時(shí)）試題名稱eaergybudgetispdistal目錄eaergybudgetispdigital輸入文件8eaergj.inbudgetinjsp.indigitaLin輸出文件Ssiergy.outbudget.ontjsp.outdigital.out附I）口文件無無無無時(shí)限1秒i秒i秒ri秒關(guān)于競賽中不同語言使用限制的說明一.關(guān)于使用Pascal語言與編譯結(jié)果的說明1.對(duì)于Pascal語言的程序，當(dāng)使用IDE和fpc編譯結(jié)果不一致時(shí)，以fpc的編譯結(jié)果為準(zhǔn)。2.允許使用數(shù)學(xué)庫（usesmath子句），以及ansistring。但不允許使用編譯開關(guān)（最后測試時(shí)pascal的范圍檢查開關(guān)默認(rèn)關(guān)閉：｛$R-,Q-,S-｝）,也不支持與優(yōu)化相關(guān)的選項(xiàng)。二.關(guān)于C++語言中模板使用的限制說明1.允許使用的部分：標(biāo)準(zhǔn)容器中的布爾集合，迭代器，串，流。相關(guān)的頭文件：<bitset><iterator><string><iostream>2.禁止使用的部分：序列：vector,list,deque序列適配器：stack,queue,priority_queue關(guān)聯(lián)容器：map,multimap,set,multiset擬容器：valarray散列容器：hash_map,hash_set,hash_multimap,hash_multiset所有的標(biāo)準(zhǔn)庫算法102004?2013年NOIP復(fù)賽試題集(提高組)相關(guān)頭文件：<vector><list><deque><stack><map><set><algorithm>.能量項(xiàng)鏈(energy.pas/c/cpp)【問題描述】在Mars星球上，每個(gè)Mars人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有N顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過吸盤(吸盤是Mars人吸收能量的一種器官)的作用，這兩顆珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為n，則聚合后釋放的能量為m*r*n(Mars單位)，新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。需要時(shí)，Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請(qǐng)你設(shè)計(jì)一個(gè)聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。例如：設(shè)N=4,4顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2,3)(3,5)(5,10)(10，2)。我們用記號(hào)十表示兩顆珠子的聚合操作，。十k)表示第j，k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能量為：(4十1)=10*2*3=60。這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放的總能量為((4十1)十2)十3)=10*2*3+10*3*5+10*5*10=710。【輸入文件】輸入文件energy.in的第一行是一個(gè)正整數(shù)N(4WNW100)，表示項(xiàng)鏈上珠子的個(gè)數(shù)。第二行是N個(gè)用空格隔開的正整數(shù)，所有的數(shù)均不超過1000。第i個(gè)數(shù)為第i顆珠子的頭標(biāo)記(1WiWN)，當(dāng)i<N時(shí)，第i顆珠子的尾標(biāo)記應(yīng)該等于第i+1顆珠子的頭標(biāo)記。第N顆珠子的尾標(biāo)記應(yīng)該等于第1顆珠子的頭標(biāo)記。至于珠子的順序，你可以這樣確定：將項(xiàng)鏈放到桌面上，不要出現(xiàn)交叉，隨意指定第一顆珠子，然后按順時(shí)針方向確定其他珠子的順序?！据敵鑫募枯敵鑫募nergy.out只有一行，是一個(gè)正整數(shù)E(EW2.1*109)，為一個(gè)最優(yōu)聚合順序所釋放的總能量?！据斎霕永?23510【輸出樣例】71011

2004?2013年NOIP復(fù)賽試題集（提高組）.金明的預(yù)算方案（budget.pas/c/cpp）【問題描述】如果要買歸類為附件的物品，必須先買該附件所屬的主件附件主件。每個(gè)主件可以有如果要買歸類為附件的物品，必須先買該附件所屬的主件附件主件。每個(gè)主件可以有0個(gè)、1個(gè)或2個(gè)附件。附件不再有電腦打印機(jī)，掃描儀從屬于自己的附件。金明想買的東西很多，肯定會(huì)超過媽書柜圖書媽限定的N元。于是，他把每件物品規(guī)定了一個(gè)重要度，書桌臺(tái)燈，文具分為5等：用整數(shù)1?5表示，第5等最重要。他還從因特工作椅無網(wǎng)上查到了每件物品的價(jià)格（都是10元的整數(shù)倍）。他希 望在不超過N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。設(shè)第j件物品的價(jià)格為v[j]，重要度為w[j]，共選中了k件物品，編號(hào)依次為j1，j2,……，jk，則所求的總和為：v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。（其中*為乘號(hào)）請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購物單。【輸入文件】輸入文件budget.in的第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開：nm（其中N（＜32000）表示總錢數(shù)，m（＜60）為希望購買物品的個(gè)數(shù)。）從第2行到第m+1行，第j行給出了編號(hào)為j-1的物品的基本數(shù)據(jù)，每行有3個(gè)非負(fù)整數(shù)vpq（其中v表示該物品的價(jià)格（v＜10000），p表示該物品的重要度（1?5），q表示該物品是主件還是附件。如果q=0，表示該物品為主件，如果q＞0，表示該物品為附件，q是所屬主件的編號(hào)）【輸出文件】輸出文件budget.out只有一個(gè)正整數(shù)，為不超過總錢數(shù)的物品的價(jià)格與重要度乘積的總和的最大值（＜200000）?！据斎霕永?00058002040051300514003050020【輸出樣例】2200122004?2013年NOIP復(fù)賽試題集（提高組）3.作業(yè)調(diào)度方案（jsp.pas/c/cpp）【問題描述】我們現(xiàn)在要利用m臺(tái)機(jī)器加工n個(gè)工件，每個(gè)工件都有m道工序，每道工序都在不同的指定的機(jī)器上完成。每個(gè)工件的每道工序都有指定的加工時(shí)間。每個(gè)工件的每個(gè)工序稱為一個(gè)操作，我們用記號(hào)j-k表示一個(gè)操作，其中j為1到n中的某個(gè)數(shù)字，為工件號(hào)；k為1到m中的某個(gè)數(shù)字，為工序號(hào)，例如2-4表示第2個(gè)工件第4道工序的這個(gè)操作。在本題中，我們還給定對(duì)于各操作的一個(gè)安排順序。例如，當(dāng)n=3,m=2時(shí)，“1-1,1-2,2-1,3-1,3-2,2-2”就是一個(gè)給定的安排順序，即先安排第1個(gè)工件的第1個(gè)工序，再安排第1個(gè)工件的第2個(gè)工序，然后再安排第2個(gè)工件的第1個(gè)工序，等等。一方面，每個(gè)操作的安排都要滿足以下的兩個(gè)約束條件。（1）對(duì)同一個(gè)工件，每道工序必須在它前面的工序完成后才能開始；（2）同一時(shí)刻每一臺(tái)機(jī)器至多只能加工一個(gè)工件。另一方面，在安排后面的操作時(shí)，不能改動(dòng)前面已安排的操作的工作狀態(tài)。由于同一工件都是按工序的順序安排的，因此，只按原順序給出工件號(hào)，仍可得到同樣的安排順序，于是，在輸入數(shù)據(jù)中，我們將這個(gè)安排順序簡寫為“112332”。還要注意，“安排順序”只要求按照給定的順序安排每個(gè)操作。不一定是各機(jī)器上的實(shí)際操作順序。在具體實(shí)施時(shí)，有可能排在后面的某個(gè)操作比前面的某個(gè)操作先完成。例如，取n=3,m=2,E知數(shù)據(jù)如下：工件號(hào)機(jī)器號(hào)/加工時(shí)間工序1工序211/32/221/22/532/21/4則對(duì)于安排順序“112332”，下圖中的兩個(gè)實(shí)施方案都是正確的。但所需要的總時(shí)間分別是10與12。當(dāng)一個(gè)操作插入到某臺(tái)機(jī)器的某個(gè)空檔時(shí)（機(jī)器上最后的尚未安排操作的部分也可以看作一個(gè)空檔），可以靠前插入，也可以靠后或居中插入。為了使問題簡單一些，我們約定：在保證約束條件（1）（2）的條件下，盡量靠前插入。并且，我們還約定，如果有多個(gè)空檔可以插入，就在保證約束條件（1）（2）的條件下，插入到最前面的一個(gè)空檔。于是，在這些約定下，上例中的方案一是正確的，而方案二是不正確的。顯然，在這些約定下，對(duì)于給定的安排順序，符合該安排順序的實(shí)施方案是唯一的，請(qǐng)你計(jì)算出該方案完成全部任務(wù)所需的總時(shí)間?！据斎胛募枯斎胛募sp.in的第1行為兩個(gè)正整數(shù)，用一個(gè)空格隔開：mn（其中m（＜20）表示機(jī)器數(shù)，n（＜20）表示工件數(shù)）第2行：個(gè)用空格隔開的數(shù)，為給定的安排順序。接下來的2n行，每行都是用空格隔開的m個(gè)正整數(shù)，每個(gè)數(shù)不超過20。其中前n行依次表示每個(gè)工件的每個(gè)工序所使用的機(jī)器號(hào)，第1個(gè)數(shù)為第1個(gè)工序的機(jī)器號(hào)，第2個(gè)數(shù)為第2個(gè)工序機(jī)器號(hào)，等等。后n行依次表示每個(gè)工件的每個(gè)工序的加工時(shí)間?？梢员ＷC，以上各數(shù)據(jù)都是正確的，不必檢驗(yàn)。132004?2013年NOIP復(fù)賽試題集（提高組）【輸出文件】輸出文件jsp.out只有一個(gè)正整數(shù)，為最少的加工時(shí)間?！据斎霕永?3112332121221322524【輸出樣例】10142004?2013年NOIP復(fù)賽試題集（提高組）2k進(jìn)制數(shù)（digital.pas/c/cpp）【問題描述】設(shè)r是個(gè)2k進(jìn)制數(shù)，并滿足以下條件：（1）r至少是個(gè)2位的2k進(jìn)制數(shù)。（2）作為2k進(jìn)制數(shù)，除最后一位外，r的每一位嚴(yán)格小于它右邊相鄰的那一位。（3）將r轉(zhuǎn)換為2進(jìn)制數(shù)q后，則q的總位數(shù)不超過w。在這里，正整數(shù)k（1WkW9）和w（k<wW30000）是事先給定的。問：滿足上述條件的不同的r共有多少個(gè)？我們?cè)購牧硪唤嵌茸餍┙忉專涸O(shè)S是長度為w的01字符串（即字符串S由w個(gè)“0”或“1”組成），S對(duì)應(yīng)于上述條件（3）中的q。將S從右起劃分為若干個(gè)長度為k的段，每段對(duì)應(yīng)一位2k進(jìn)制的數(shù)，如果S至少可分成2段，則S所對(duì)應(yīng)的二進(jìn)制數(shù)又可以轉(zhuǎn)換為上述的2k進(jìn)制數(shù)r。例：設(shè)k=3,w=7。貝h是個(gè)八進(jìn)制數(shù)（23=8）。由于w=7,長度為7的01字符串按3位一段分，可分為3段（即1,3,3,左邊第一段只有一個(gè)二進(jìn)制位），則滿足條件的八進(jìn)制數(shù)有：2位數(shù)：高位為1：6個(gè)（即12,13,14,15,16,17）,高位為2：5個(gè)，…，高位為6：1個(gè)（即67）。共6+5+…+1=21個(gè)。3位數(shù)：高位只能是1,第2位為2：5個(gè)（即123,124,125,126,127）,第2位為3：4個(gè)，…，第2位為6：1個(gè)（即167）。共5+4+-+1=15個(gè)。所以，滿足要求的r共有36個(gè)?！据斎胛募枯斎胛募igital.in只有1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開：kw【輸出文件】輸出文件digital.out為1行，是一個(gè)正整數(shù)，為所求的計(jì)算結(jié)果，即滿足條件的不同恤的個(gè)數(shù)（用十進(jìn)制數(shù)表示），要求最高位不得為0,各數(shù)字之間不得插入數(shù)字以外的其他字符（例如空格、換行符、逗號(hào)等）。（提示：作為結(jié)果的正整數(shù)可能很大，但不會(huì)超過200位）【輸入樣例】37【輸出樣例】36152004?2013年NOIP復(fù)賽試題集（提高組）第十三屆全國信息學(xué)奧林匹克分區(qū)聯(lián)賽（NOIP2007）復(fù)賽試題（提高組競賽用時(shí)：3小時(shí)）寇目名稱統(tǒng)計(jì)數(shù)字n字符串的展開矩陣曬數(shù)游戲樹網(wǎng)的修代號(hào)countexpand.gznnccore輸人文沖cowit.inexpandLingam已向cnre.in輸出々件comt.outexpand.aitgame.outcore,out時(shí)限1秒1秒1杪】杪說明:.文件名（程序名和輸入輸出文件名）必須使用小寫.C/C++中函數(shù)main（）的返回值類型必須是int，程序正常結(jié)束時(shí)的返回值必須是0。3.全國統(tǒng)一評(píng)測時(shí)采用的機(jī)器參考配置為：CPU2.0GHz,內(nèi)存256M。1、統(tǒng)計(jì)數(shù)字（count.pas/c/cpp）【問題描述】某次科研調(diào)查時(shí)得到了n個(gè)自然數(shù)，每個(gè)數(shù)均不超過1500000000（1.5*109）。已知不相同的數(shù)不超過10000個(gè)，現(xiàn)在需要統(tǒng)計(jì)這些自然數(shù)各自出現(xiàn)的次數(shù)，并按照自然數(shù)從小到大的順序輸出統(tǒng)計(jì)結(jié)果?！据斎搿枯斎胛募ount.in包含n+1行；第一行是整數(shù)n，表示自然數(shù)的個(gè)數(shù)；第2?n+1每行一個(gè)自然數(shù)。【輸出】輸出文件count.out包含m行（m為9個(gè)自然數(shù)中不相同數(shù)的個(gè)數(shù)），按照自然數(shù)從小到大的順序輸出。每行輸出兩個(gè)整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù)，其間用一個(gè)空格隔開?！据斎胼敵鰳永縞ount.incount.out82324216

2004?2013年NOIP復(fù)賽試題集（提高組）【限制】40%的數(shù)據(jù)滿足：1<=n<=100080%的數(shù)據(jù)滿足：1<=n<=50000100%的數(shù)據(jù)滿足：1<=n<=200000，每個(gè)數(shù)均不超過1500000000（1.5*109）172004?2013年NOIP復(fù)賽試題集(提高組)2、字符串的展開(expand.pas/c/cpp)【問題描述】在初賽普及組的“閱讀程序?qū)懡Y(jié)果”的問題中，我們?cè)o出一個(gè)字符串展開的例子：如果在輸入的字符串中，含有類似于“d-h”或者“4-8”的字串，我們就把它當(dāng)作一種簡寫，輸出時(shí)，用連續(xù)遞增的字母獲數(shù)字串替代其中的減號(hào)，即，將上面兩個(gè)子串分別輸出為“defgh”和“45678”。在本題中，我們通過增加一些參數(shù)的設(shè)置，使字符串的展開更為靈活。具體約定如下：(1)遇到下面的情況需要做字符串的展開：在輸入的字符串中，出現(xiàn)了減號(hào)“-"，減號(hào)兩側(cè)同為小寫字母或同為數(shù)字，且按照ASCII碼的順序，減號(hào)右邊的字符嚴(yán)格大于左邊的字符。(2)參數(shù)p1：展開方式。p1=1時(shí)，對(duì)于字母子串，填充小寫字母；p1=2時(shí)，對(duì)于字母子串，填充大寫字母。這兩種情況下數(shù)字子串的填充方式相同。p1=3時(shí)，不論是字母子串還是數(shù)字字串，都用與要填充的字母個(gè)數(shù)相同的星號(hào)“*”來填充。(3)參數(shù)p2：填充字符的重復(fù)個(gè)數(shù)。p2=k表示同一個(gè)字符要連續(xù)填充k個(gè)。例如，當(dāng)p2=3時(shí)，子串“d-h”應(yīng)擴(kuò)展為“deeefffgggh"。減號(hào)兩邊的字符不變。(4)參數(shù)p3：是否改為逆序：p3=1表示維持原來順序，p3=2表示采用逆序輸出，注意這時(shí)候仍然不包括減號(hào)兩端的字符。例如當(dāng)p1=1、p2=2、p3=2時(shí)，子串“d-h”應(yīng)擴(kuò)展為“dggffeeh”。(5)如果減號(hào)右邊的字符恰好是左邊字符的后繼，只刪除中間的減號(hào)，例如：“d-e”應(yīng)輸出為“de”，“3-4”應(yīng)輸出為“34”。如果減號(hào)右邊的字符按照ASCII碼的順序小于或等于左邊字符，輸出時(shí)，要保留中間的減號(hào)，例如：“d-d”應(yīng)輸出為“d-d”，“3-1”應(yīng)輸出為“3-1”?！据斎搿枯斎胛募xpand.in包括兩行：第1行為用空格隔開的3個(gè)正整數(shù)，一次表示參數(shù)p1，p2，p3。第2行為一行字符串，僅由數(shù)字、小寫字母和減號(hào)“-”組成。行首和行末均無空格。【輸出】輸出文件expand.out只有一行，為展開后的字符串?！据斎胼敵鰳永?】expand.inexpand.out121abcs-w1234-9s-4zzabcsttuuvvw1234556677889s-4zz【輸入輸出樣例2】expand.inexpand.out232a-d-daCCCBBBd-d【輸入輸出樣例3】expand.inexpand.out342di-jkstra2-6dijkstra2************6【限制】40%的數(shù)據(jù)滿足：字符串長度不超過5100%的數(shù)據(jù)滿足：1<=p1<=3，1<=p2<=8，1<=p3<=2。字符串長度不超過100182004?2013年NOIP復(fù)賽試題集（提高組）3、矩陣取數(shù)游戲（game.pas/c/cpp）【問題描述】帥帥經(jīng)常更同學(xué)玩一個(gè)矩陣取數(shù)游戲：對(duì)于一個(gè)給定的n*m的矩陣，矩陣中的每個(gè)元素aij均為非負(fù)整數(shù)。游戲規(guī)則如下：.每次取數(shù)時(shí)須從每行各取走一個(gè)元素，共n個(gè)。m次后取完矩陣所有的元素；.每次取走的各個(gè)元素只能是該元素所在行的行首或行尾；.每次取數(shù)都有一個(gè)得分值，為每行取數(shù)的得分之和；每行取數(shù)的得分;被取走的元素值*2i，其中i表示第i次取數(shù)（從1開始編號(hào)）；.游戲結(jié)束總得分為m次取數(shù)得分之和。帥帥想請(qǐng)你幫忙寫一個(gè)程序，對(duì)于任意矩陣，可以求出取數(shù)后的最大得分?！据斎搿枯斎胛募ame.in包括n+1行；第一行為兩個(gè)用空格隔開的整數(shù)n和m01+2+（2+3）*4+8*6第2?n+1行為n*m矩陣，其中每行有m個(gè)用單個(gè)空格隔開【輸出】輸出文件game.out僅包含1行，為一個(gè)整數(shù)，即輸入矩陣取數(shù)后的最大的分?！据斎胼敵鰳永?】game.ingame.out2382123342【輸入輸出樣例1解釋】第1次：第一行取行首元素，第二行取行尾元素，本次的氛圍1*21+2*21=6第2次：兩行均取行首元素，本次得分為2*22+3*22=20第3次：得分為3*23+4*23=56?？偟梅譃?+20+56=82【輸入輸出樣例2】game.ingame.out144505122【輸入輸出樣例3】game.ingame.out2103169949656544686122388804316951829305388836467【限制】60%的數(shù)據(jù)滿足：1<=n,100%的數(shù)據(jù)滿足：1<=n,m<=30,答案不超過1016m<=80,0<=aij<=1000192004?2013年NOIP復(fù)賽試題集(提高組)4、樹網(wǎng)的核(core.pas/c/cpp)【問題描述】設(shè)T=(V,E,W)是一個(gè)無圈且連通的無向圖(也稱為無根樹)，每條邊到有正整數(shù)的權(quán)，我們稱T為樹網(wǎng)(treebetwork),其中V,E分別表示結(jié)點(diǎn)與邊的集合，W表示各邊長度的集合，并設(shè)T有n個(gè)結(jié)點(diǎn)。路徑：樹網(wǎng)中任何兩結(jié)點(diǎn)a，b都存在唯一的一條簡單路徑，用d(a,b)表示以a,b為端點(diǎn)的路徑的長度，它是該路徑上各邊長度之和。我們稱d(a,b)為a,b兩結(jié)點(diǎn)間的距離。D(v,P)=min{d(v,u),u為路徑P上的結(jié)點(diǎn)}。樹網(wǎng)的直徑：樹網(wǎng)中最長的路徑成為樹網(wǎng)的直徑。對(duì)于給定的樹網(wǎng)T，直徑不一定是唯一的，但可以證明：各直徑的中點(diǎn)(不一定恰好是某個(gè)結(jié)點(diǎn)，可能在某條邊的內(nèi)部)是唯一的，我們稱該點(diǎn)為樹網(wǎng)的中心。偏心距ECC(F):樹網(wǎng)T中距路徑F最遠(yuǎn)的結(jié)點(diǎn)到路徑F的距離，即ECC(F)=max{d(v,F),v6}任務(wù)：對(duì)于給定的樹網(wǎng)T=(V,E,W)和非負(fù)整數(shù)s,求一個(gè)路徑F,他是某直徑上的一段路徑(該路徑兩端均為樹網(wǎng)中的結(jié)點(diǎn))，其長度不超過s(可以等于s),使偏心距￡口任)最小。我們稱這個(gè)路徑為樹網(wǎng)T=(V,E,W)的核(Core)。必要時(shí)，F(xiàn)可以退化為某個(gè)結(jié)點(diǎn)。一般來說，在上述定義下，核不一定只有一個(gè)，但最小偏心距是唯一的。下面的圖給出了樹網(wǎng)的一個(gè)實(shí)例。圖中，A-B與A-C是兩條直徑，長度均為20。點(diǎn)W是樹網(wǎng)的中心，EF邊的長度為5。如果指定s=11,則樹網(wǎng)的核為路徑DEFG(也可以取為路徑DEF),偏心距為8。如果指定s=0(或s=1、s=2),則樹網(wǎng)的核為結(jié)點(diǎn)F,偏心距為12?！据斎搿枯斎胛募ore.in包含n行：第1行，兩個(gè)正整數(shù)n和s,中間用一個(gè)空格隔開。其中n為樹網(wǎng)結(jié)點(diǎn)的個(gè)數(shù)，s為樹網(wǎng)的核的長度的上界。設(shè)結(jié)點(diǎn)編號(hào)以此為1,2,……，n。從第2行到第n行，每行給出3個(gè)用空格隔開的正整數(shù)，依次表示每一條邊的兩個(gè)端點(diǎn)編號(hào)和長度。例如，“247”表示連接結(jié)點(diǎn)2與4的邊的長度為7。所給的數(shù)據(jù)都是爭取的，不必檢驗(yàn)。20

2004?2013年NOIP復(fù)賽試題集（提高組）【輸出】輸出文件core.out只有一個(gè)非負(fù)整數(shù)，為指定意義下的最小偏心距?！据斎胼敵鰳永?】core.inCore.out525125232244253【輸入輸出樣例2】core.incore.out865132232346453464472783【限制】40%的數(shù)據(jù)滿足：5<=n<=1570%的數(shù)據(jù)滿足：5<=n<=80100%的數(shù)據(jù)滿足：5<=n<=300，0<=s<=1000。邊長度為不超過1000的正整數(shù)21

2004?2013年NOIP復(fù)賽試題集（提高組）第十四屆全國信息學(xué)奧林匹克分區(qū)聯(lián)賽（NOIP2008）復(fù)賽試題（提高組競賽用時(shí)：3小時(shí)）、題目概覽中文題目名稱笨小猴火柴棒等式傳紙條雙棧排序英文題目名稱wordmatchesmessagetwostack可執(zhí)行文件名wordmatchesmessagetwostack輸入文件名word,wostack.in輸出文件名word.outmatches.outmessage.outtwostack.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)二、提交源程序文件名對(duì)于Pascal語言word.pasmatches.pasmessage.pastwostack.pas對(duì)于C語言word.cmatches.cmessage.ctwostack.c對(duì)于C++語言word.cppmatches.cppmessage.cpptwostack.cpp三、編譯命令（不包含任何優(yōu)化開關(guān)）對(duì)于Pascal語言fpcword.pasfpcmatches.pasfpcmessage.pasfpctwostack.pas對(duì)于C語言gcc-owordword.cgcc-omatchesmatches.cgcc-omessagemessage.cgcc-otwostacktwostack.c對(duì)于C++語言g++-owordword.cppg++-omatchesmatches.cppg++-omessagemessage.cppg++-otwostacktwostack.cpp四、運(yùn)行內(nèi)存限制運(yùn)行內(nèi)存上限50M50M運(yùn)行內(nèi)存上限50M50M50M50M注意事項(xiàng)：.文件名（程序名和輸入輸出文件名）必須使用大寫。.C/C++中函數(shù)main（）的返回值類型必須是int，程序正常結(jié)束時(shí)的返回值必須是0。.全國統(tǒng)一評(píng)測時(shí)采用的機(jī)器配置為：CPU1.9GHz,內(nèi)存512M，上述時(shí)限以此配置為準(zhǔn)。各省在自測時(shí)可根據(jù)具體配置調(diào)整時(shí)限。.笨小猴（word.pas/c/cpp）【問題描述】笨小猴的詞匯量很小，所以每次做英語選擇題的時(shí)候都很頭疼。但是他找到了一種方法，經(jīng)試222004?2013年NOIP復(fù)賽試題集（提高組）驗(yàn)證明，用這種方法去選擇選項(xiàng)的時(shí)候選對(duì)的幾率非常大！這種方法的具體描述如下：假設(shè)maxn是單詞中出現(xiàn)次數(shù)最多的字母的出現(xiàn)次數(shù)，minn是單詞中出現(xiàn)次數(shù)最少的字母的出現(xiàn)次數(shù)，如果maxn-minn是一個(gè)質(zhì)數(shù)，那么笨小猴就認(rèn)為這是個(gè)LuckyWord，這樣的單詞很可能就是正確的答案。【輸入】輸入文件word.in只有一行，是一個(gè)單詞，其中只可能出現(xiàn)小寫字母，并且長度小于100?！据敵觥枯敵鑫募ord.out共兩行，第一行是一個(gè)字符串，假設(shè)輸入的的單詞是LuckyWord,那么輸出“LuckyWord”，否則輸出“NoAnswer”；第二行是一個(gè)整數(shù)，如果輸入單詞是LuckyWord,輸出maxn-minn的值，否則輸出0?！据斎胼敵鰳永?】word.inword.outerrorLuckyWord2【輸入輸出樣例1解釋】單詞error中出現(xiàn)最多的字母r出現(xiàn)了3次，出現(xiàn)次數(shù)最少的字母出現(xiàn)了1次，3-1=2,2是質(zhì)數(shù)?！据斎胼敵鰳永?】word.inword.outolympicNoAnswer0【輸入輸出樣例2解釋】單詞olympic中出現(xiàn)最多的字母i出現(xiàn)了2次，出現(xiàn)次數(shù)最少的字母出現(xiàn)了1次，2-1=1，1不是質(zhì)數(shù)。232004?2013年NOIP復(fù)賽試題集（提高組）.火柴棒等式（matches.pas/c/cpp）【問題描述】給你n根火柴棍，你可以拼出多少個(gè)形如"A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整數(shù)（若該數(shù)非零，則最高位不能是0）。用火柴棍拼數(shù)字0-9的拼法如圖所示：??*?iIiJiin iiiHii注意：1）加號(hào)與等號(hào)各自需要兩根火柴棍2）如果A9，則A+B=C與B+A=C視為不同的等式（A、B、C>=0）3）n根火柴棍必須全部用上【輸入】輸入文件matches.in共一行，又一個(gè)整數(shù)n（n<=24）。【輸出】輸出文件matches.out共一行，表示能拼成的不同等式的數(shù)目?！据斎胼敵鰳永?】matches.inmatches.out142【輸入輸出樣例1解釋】2個(gè)等式為0+1=1和1+0=1?！据斎胼敵鰳永?】matches.inmatches.out189【輸入輸出樣例2解釋】9個(gè)等式為：0+4=40+11=111+10=112+2=42+7=94+0=47+2=910+1=1111+0=11242004?2013年NOIP復(fù)賽試題集(提高組).傳紙條(message.pas/c/cpp)【問題描述】小淵和小軒是好朋友也是同班同學(xué)，他們?cè)谝黄鹂傆姓劜煌甑脑掝}。一次素質(zhì)拓展活動(dòng)中，班上同學(xué)安排做成一個(gè)m行n列的矩陣，而小淵和小軒被安排在矩陣對(duì)角線的兩端，因此，他們就無法直接交談了。幸運(yùn)的是，他們可以通過傳紙條來進(jìn)行交流。紙條要經(jīng)由許多同學(xué)傳到對(duì)方手里，小淵坐在矩陣的左上角，坐標(biāo)(1,1)，小軒坐在矩陣的右下角，坐標(biāo)(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。在活動(dòng)進(jìn)行中，小淵希望給小軒傳遞一張紙條，同時(shí)希望小軒給他回復(fù)。班里每個(gè)同學(xué)都可以幫他們傳遞，但只會(huì)幫他們一次，也就是說如果此人在小淵遞給小軒紙條的時(shí)候幫忙，那么在小軒遞給小淵的時(shí)候就不會(huì)再幫忙。反之亦然。還有一件事情需要注意，全班每個(gè)同學(xué)愿意幫忙的好感度有高有低(注意：小淵和小軒的好心程度沒有定義，輸入時(shí)用0表示)，可以用一個(gè)0-100的自然數(shù)來表示，數(shù)越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學(xué)來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學(xué)的好心程度只和最大?，F(xiàn)在，請(qǐng)你幫助小淵和小軒找到這樣的兩條路徑?！据斎搿枯斎胛募essage.in的第一行有2個(gè)用空格隔開的整數(shù)m和n，表示班里有m行n列(1<=m,n<=50)。接下來的m行是一個(gè)m*n的矩陣，矩陣中第i行j列的整數(shù)表示坐在第i行j列的學(xué)生的好心程度。每行的n個(gè)整數(shù)之間用空格隔開?！据敵觥枯敵鑫募essage.out共一行，包含一個(gè)整數(shù)，表示來回兩條路上參與傳遞紙條的學(xué)生的好心程度之和的最大值。【輸入輸出樣例】message.inmessage.out3334039285570【限制】30%的數(shù)據(jù)滿足：1<=m,n<=10100%的數(shù)據(jù)滿足：1<=m,n<=50252004?2013年NOIP復(fù)賽試題集(提高組).雙棧排序(twostack.pas/c/cpp)【問題描述】Tom最近在研究一個(gè)有趣的排序問題。如圖所示，通過2個(gè)棧S1和S2,Tom希望借助以下4種操作實(shí)現(xiàn)將輸入序列升序排序。操作a：如果輸入序列不為空，將第一個(gè)元素壓入棧S1 操作b：如果棧S1不為空，將S1棧頂元素彈出至輸出序列 'I 操作c：如果輸入序列不為空，將第一個(gè)元素壓入棧S2 號(hào)2操作d：如果棧S2不為空，將S2棧頂元素彈出至輸出序列 . 如果一個(gè)1?n的排列P可以通過一系列操作使得輸出序列為1，2,…，(n-1)，n，Tom就稱P是一個(gè)“可雙棧排序排列”。例如(1,3,2,4)就是一個(gè)“可雙棧排序序列”，而(2,3,4,1)不是。下圖描述了一個(gè)將(1,3,2,4)排序的操作序列：＜a,c,c,b,a,d,d,b＞當(dāng)然，這樣的操作序列有可能有幾個(gè)，對(duì)于上例(1,3,2,4)，＜a,c,c,b,a,d,d,b＞是另外一個(gè)可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么?！据斎搿枯斎胛募wostack.in的第一行是一個(gè)整數(shù)n。第二行有n個(gè)用空格隔開的正整數(shù)，構(gòu)成一個(gè)1?n的排列?！据敵觥枯敵鑫募wostack.out共一行，如果輸入的排列不是“可雙棧排序排列"，輸出數(shù)字0；否則輸262004?2013年NOIP復(fù)賽試題集（提高組）出字典序最小的操作序列，每兩個(gè)操作之間用空格隔開，行尾沒有空格。【輸入輸出樣例1】wostack.out41324abaabbab【輸入輸出樣例2】wostack.out423410【輸入輸出樣例3】wostack.out3231acabbd【限制】30%的數(shù)據(jù)滿足：n<=1050%的數(shù)據(jù)滿足：n<=50100%的數(shù)據(jù)滿足：n<=100027

2004?2013年NOIP復(fù)賽試題集（提高組）第十五屆全國信息學(xué)奧林匹克分區(qū)聯(lián)賽（NOIP2009）復(fù)賽試題一.（提高組競賽用時(shí)：3小時(shí)）一.題目概況中文題目名稱潛伏者Hanksqn的趣味題最優(yōu)貿(mào)易靶形數(shù)獨(dú)英文題目名稱spysontradesudoku可執(zhí)行文件常spysontradesudoku輸入文件名spyJnsoniutrade.insudoku.in輸出文件名spy.outson.outtrade.outsudoku.out每個(gè)測試點(diǎn)時(shí)限1秒1秒1秒2秒測試點(diǎn)數(shù)目1ULi1020每個(gè)蒯試點(diǎn)分值1ULi105附加樣例文件有有有有結(jié)果比較方式全文比較過濾行末空格及文末回車全文比較過濾行末空格及文末回車全文比較過濾行末空格及文末回車全文比較過濾行末空格及文末回車題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)傳統(tǒng)二.提交程序文件名對(duì)于pascal語言spy.passon.pastrade.pEissudoku,pas對(duì)于C語言spycson.cIrade.csudcku.c對(duì)于C+十語言spyxppsonxpptrade,cppsudokuxpp三.編譯命令（不包含任何優(yōu)化開關(guān)）對(duì)于pascal語言fpcspy.pasfpcsmpasfpctrade.pEisfpcsudoku,pas對(duì)于C語言gcc-ospyspyc-Imgcc-osonsons-Imgcc-otradetrade,c-Imgcc-osudokusudoku.c-Im對(duì)于C++語言十-ospyspyxpp-Img++-050Tlson.cpp-Img-H--otradetrade.cpp-Img十十-osudokusudoku.cpp-Im四.運(yùn)行內(nèi)存限制282004?2013年NOIP復(fù)賽試題集（提高組）內(nèi)存上限128M128M128M128M注意事項(xiàng)：1、文件名（程序名和輸入輸出文件名）必須使用小寫。2、C/C++中函數(shù)main（）的返回值類型必須是int，程序正常結(jié)束時(shí)的返回值必須是0。3、全國統(tǒng)一評(píng)測時(shí)采用的機(jī)器配置為：CPU1.9GHz,內(nèi)存1G，上述時(shí)限以此配置為準(zhǔn)。各省在自測時(shí)可根據(jù)具體配置調(diào)整時(shí)限。1、潛伏者（spy.pas/c/cpp）【問題描述】R國和S國正陷入戰(zhàn)火之中，雙方都互派間諜，潛入對(duì)方內(nèi)部，伺機(jī)行動(dòng)。歷經(jīng)艱險(xiǎn)后，潛伏于S國的R國間諜小C終于摸清了S國軍用密碼的編碼規(guī)則：1）S國軍方內(nèi)部欲發(fā)送的原信息經(jīng)過加密后在網(wǎng)絡(luò)上發(fā)送，原信息的內(nèi)容與加密后所的內(nèi)容均由大寫字母‘A’一‘Z’構(gòu)成（無空格等其他字母）。2）S國對(duì)于每個(gè)字母規(guī)定了對(duì)應(yīng)的“密字”。加密的過程就是將原信息中的所有字母替換為其對(duì)應(yīng)的“密字”。3）每個(gè)字母只對(duì)應(yīng)一個(gè)唯一的“密字”，不同的字母對(duì)應(yīng)不同的“密字”?！懊茏帧笨梢院驮帜赶嗤＠?，若規(guī)定‘A’的密字為‘A’，‘B’的密字為‘C’（其他字母及密字略），則原信息“ABA”被加密為“ACA”。現(xiàn)在，小C通過內(nèi)線掌握了S國網(wǎng)絡(luò)上發(fā)送的一條加密信息及其對(duì)應(yīng)的原信息。小C希望能通過這條信息，破譯S國的軍用密碼。小C的破譯過程是這樣的：掃描原信息，對(duì)于原信息中的字母x（代表任一大寫字母），找督其在加密信息中的對(duì)應(yīng)大寫字母y，并認(rèn)為在密碼里y是x的密字。如此進(jìn)行下去直到停止于如下的某個(gè)狀態(tài)：1）所有信息掃描完畢，‘A'一‘Z’所有26個(gè)字母在原信息中均出現(xiàn)過并獲得了相應(yīng)的“密字”。2）所有信息掃描完畢，但發(fā)現(xiàn)存在某個(gè)（或某些）字母在原信息中沒有出現(xiàn)。3）掃描中發(fā)現(xiàn)掌握的信息里有明顯的自相矛盾或錯(cuò)誤（違反S過密碼的編碼規(guī)則）。例如某條信息“XYZ”被翻譯為“ABA”就違反了“不同字母對(duì)應(yīng)不同密字”的規(guī)則。在小C忙得頭昏腦脹之際，R國司令部又發(fā)來電報(bào)，要求他翻譯另外一條從S國剛剛截取到的加密信息?，F(xiàn)在請(qǐng)你幫助小C：通過內(nèi)線掌握的信息，嘗試破譯密碼。然后利用破譯的密碼，翻譯電報(bào)中的加密信息。292004?2013年NOIP復(fù)賽試題集（提高組）【輸入】輸入文件名為spy.in,共3行，每行為一個(gè)長度在1到100之間的字符串。第1行為小C掌握的一條加密信息。第2行為第1行的加密信息所對(duì)應(yīng)的原信息。第3行為R國司令部要求小C翻譯的加密信息。輸入數(shù)據(jù)保證所有字符串僅由大寫字母‘A’一‘Z’構(gòu)成，且第1行長度與第2行相等?！据敵觥枯敵鑫募py.out共1行。若破譯密碼停止時(shí)出現(xiàn)2,3兩種情況，請(qǐng)你輸出“Failed”（不含引號(hào)，注意首字母大寫，其它小寫）。否則請(qǐng)輸出利用密碼翻譯電報(bào)中加密信息后得到的原信息?！据斎胼敵鰳永?】Spy.inSpy.outAAABEOWIEFailed【輸入輸出樣例說明】原信息中的字母“A”禾B”對(duì)應(yīng)相同的密字，輸出“Failed”。【輸入輸出樣例2】Spy.inSpy.outQWERTYUIOPLKJHGFDSAZXCVBNABCDEFGHIJKLMNOPQRSTUVWXYDSLIEWOFailed【輸入輸出樣例2說明】字母“Z”在原信息中沒有出現(xiàn)，輸出“Failed”。【輸入輸出樣例3】Spy.inSpy.outMSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPPYIZSDWAHLNOVFUCERKJXQMGTBPPKOIYKANZWPLLVWMQJFGQYLLFLSONOIP302004?2013年NOIP復(fù)賽試題集(提高組)2、Hankson的趣味題(son.pas/c/cpp)【問題描述】Hanks博士是BT(Bio-Tech,生物技術(shù))領(lǐng)域的知名專家，他的兒子名叫Hankson?，F(xiàn)在，剛剛放學(xué)回家的Hankson正在思考一個(gè)有趣的問題。今天在課堂上，老師講解了如何求兩個(gè)正整數(shù)c1和c2的最大公約數(shù)和最小公倍數(shù)?，F(xiàn)在Hankson認(rèn)為自己已經(jīng)熟練地掌握了這些知識(shí)，他開始思考一個(gè)“求公約數(shù)”禾求公倍數(shù)”之類問題的“逆問題”，這個(gè)問題是這樣的：已知正整數(shù)a0，a1，b0，b1，設(shè)某未知正整數(shù)x滿足：1)x和a0的最大公約數(shù)是a1；2)x和b0的最小公倍數(shù)是b1。Hankson的“逆問題”就是求出滿足條件的正整數(shù)x。但稍加思索之后，他發(fā)現(xiàn)這樣的x并不唯一，甚至可能不存在。因此他轉(zhuǎn)而開始考慮如何求解滿足條件的x的個(gè)數(shù)。請(qǐng)你幫助他編程求解這個(gè)問題?！据斎搿枯斎胛募麨閟on.in。第一行為一個(gè)正整數(shù)n，表示有n組輸入數(shù)據(jù)。接下來的n行每行一組輸入數(shù)據(jù)，為四個(gè)正整數(shù)a0，a1，b0，b1，每兩個(gè)整數(shù)之間用一個(gè)空格隔開。輸入數(shù)據(jù)保證a0能被a1整除，b1能被b0整除?！据敵觥枯敵鑫募on.out共n行。每組輸入數(shù)據(jù)的輸出結(jié)果占一行，為一個(gè)整數(shù)。對(duì)于每組數(shù)據(jù)：若不存在這樣的x，請(qǐng)輸出0；若存在這樣的x，請(qǐng)輸出滿足條件的x的個(gè)數(shù)；【輸入輸出樣例】Son.inSon.out26411962882951371776【說明】第一組輸入數(shù)據(jù)，X可以是9、18、36、72、144、288，共有6個(gè)。312004?2013年NOIP復(fù)賽試題集（提高組）第二組輸入數(shù)據(jù)，X可以是48、1776,共有2個(gè)?！緮?shù)據(jù)范圍】對(duì)于50%的數(shù)據(jù)，保證有1Wa0,bl,b0,b1W且nW100。對(duì)于100%的數(shù)據(jù)，保證有1Wa0,b1,b0,b1<2000000000且nW2000。322004?2013年NOIP復(fù)賽試題集（提高組）3、最優(yōu)貿(mào)易（trade.pas/c/cpp）【問題描述】C國有n個(gè)大城市和m條道路，每條道路連接這n個(gè)城市中的某兩個(gè)城市。任意兩個(gè)城市之間最多只有一條道路直接相連。這m條道路中有一部分為單向通行的道路，一部分為雙向通行的道路，雙向通行的道路在統(tǒng)計(jì)條數(shù)時(shí)也計(jì)為1條。C國幅員遼闊，各地的資源分布情況各不相同，這就導(dǎo)致了同一種商品在不同城市的價(jià)格不一定相同。但是，同一種商品在同一個(gè)城市的買入價(jià)和賣出價(jià)始終是相同的。商人阿龍來到C國旅游。當(dāng)他得知同一種商品在不同城市的價(jià)格可能會(huì)不同這一信息之后，便決定在旅游的同時(shí)，利用商品在不同城市中的差價(jià)賺回一點(diǎn)旅費(fèi)。設(shè)C國n個(gè)城市的標(biāo)號(hào)從1-n，阿龍決定從1號(hào)城市出發(fā)，并最終在n號(hào)城市結(jié)束自己的旅行。在旅游的過程中，任何城市可以重復(fù)經(jīng)過多次，但不要求經(jīng)過所有n個(gè)城市。阿龍通過這樣的貿(mào)易方式賺取旅費(fèi)：他會(huì)選擇一個(gè)經(jīng)過的城市邁入他最喜歡的商品一一水晶球，并在之后經(jīng)過的另一個(gè)城市賣出這個(gè)水晶球。用賺取的差價(jià)當(dāng)作旅費(fèi)。由于阿龍主要是來C國旅游，他決定這個(gè)貿(mào)易只進(jìn)行最多一次。當(dāng)然，在賺不到差價(jià)的情況下它就無需進(jìn)行貿(mào)易。假設(shè)C國有5個(gè)大城市，城市的編號(hào)和道路連接情況如下圖，單向箭頭表示這條道路為單向通行。雙向箭頭表示這條道路為雙向通行。假設(shè)1?n號(hào)城市的水晶球價(jià)格分別為4,3,5,6,1。阿龍可以選擇如下一條線路：1->2->3->5,并在2號(hào)城市以3的價(jià)格買入水晶球，在3號(hào)城市以5的價(jià)格賣出水晶球，賺取的旅費(fèi)數(shù)為2。阿龍也可以選擇如下一條線路：1->4->5->4->5,并在第1次到達(dá)5號(hào)城市時(shí)以1的價(jià)格買入水晶球，在第2次到達(dá)4號(hào)城市時(shí)以6的價(jià)格賣出水晶球，賺取的旅費(fèi)數(shù)為5?，F(xiàn)在給出n個(gè)城市的水晶球價(jià)格，m條道路的信息（每條道路所連接的兩個(gè)城市的編號(hào)以及該條道路的通行情況）。請(qǐng)你告訴阿龍，他最多能賺錢多少旅費(fèi)?！据斎搿枯斎胛募麨閠rade.in。第一行包含2個(gè)正整數(shù)n和m,中間用一個(gè)空格隔開，分別表示城市的數(shù)目和道路的數(shù)目。第二行n個(gè)正整數(shù)，每兩個(gè)正整數(shù)之間用一個(gè)空格隔開，按標(biāo)號(hào)順序分別表示這n個(gè)城市的商品價(jià)格。接下來m行，每行有3個(gè)正整數(shù)，x,y,z,每兩個(gè)整數(shù)之間用一個(gè)空格隔開。如果z=1,表示這條道路是城市x到城市y之間的單向道路；如果z=2,表示這條道路為城市x和城市y之間的雙向道路?！据敵觥枯敵鑫募rade.out共1行，包含1個(gè)整數(shù)，表示最多能賺取的旅費(fèi)。如果沒有進(jìn)行貿(mào)易，則輸332004?2013年NOIP復(fù)賽試題集（提高組）出0。【輸入輸出樣例】Trade.inTrade.out55543561121141232351452【數(shù)據(jù)范圍】輸入數(shù)據(jù)保證1號(hào)城市可以到達(dá)n號(hào)城市。對(duì)于10%的數(shù)據(jù)，1WnW6。對(duì)于30%的數(shù)據(jù)，1WnW100。對(duì)于50%的數(shù)據(jù)，不存在一條旅游路線，可以從一個(gè)城市出發(fā)，再回到這個(gè)城市。對(duì)于100%的數(shù)據(jù)，1WnW,1WmW,1Wx,yWn,1WzW2,1W各城市水晶球價(jià)格W100。342004?2013年NOIP復(fù)賽試題集（提高組）4、靶形數(shù)獨(dú)(sudokuapas/c/cpp)【問題描述】小城和小華都是熱愛數(shù)學(xué)的好學(xué)生，最近，他們不約而同地迷上了數(shù)獨(dú)游戲，好勝的他們想用數(shù)獨(dú)來一比高堤但普通的數(shù)獨(dú)對(duì)他們來說都過于簡單了，于是他們向Z博士請(qǐng)教，Z博士拿出了他最近發(fā)明的“靶形數(shù)獨(dú)”，作為這兩個(gè)孩子比試的題目。靶形數(shù)獨(dú)的方格同普通數(shù)獨(dú)一樣，在9格寬X9格高的大九宮格中有9個(gè)3格寬X3格高的小九宮格（用粗黑色線隔開的）。在這個(gè)大九宮格中，有一些數(shù)字是已知的，根據(jù)這些數(shù)字，利用邏輯推理，在其他的空格上填入1到9的數(shù)字。每個(gè)數(shù)字在每個(gè)小九宮格內(nèi)不能重復(fù)出現(xiàn)，每個(gè)數(shù)字在每行、每列也不能重復(fù)出現(xiàn)。但靶形數(shù)獨(dú)有一點(diǎn)和普通數(shù)獨(dú)不同，即每一個(gè)方格都有一個(gè)分值，而且如同一個(gè)靶子一樣，離中心越近則分值越高。（如下圖）上圖具體的分值分布是：最里面一格（黃色區(qū)域）為10分，黃色區(qū)域外面的一圈（紅色區(qū)域）每個(gè)格子為9分，再外面一圈（藍(lán)色區(qū)域）每個(gè)格子為8分，藍(lán)色區(qū)域外面一圈（棕色區(qū)域）每個(gè)格子為7分，最外面一圈（白色區(qū)域）每個(gè)格子為6分，如上圖所示。比賽的要求是：每個(gè)人必須完成一個(gè)給定的數(shù)獨(dú)（每個(gè)給定數(shù)獨(dú)有可能有不同的填法），而且要爭取更高的總分?jǐn)?shù)。而這個(gè)總分?jǐn)?shù)即每個(gè)方格上的分值和完成這個(gè)數(shù)獨(dú)時(shí)填在相應(yīng)格上的數(shù)字的乘積的總禾如圖，在以下這個(gè)已經(jīng)填完數(shù)字的靶形數(shù)獨(dú)游戲中，總分為2829。游戲規(guī)定，將以總分?jǐn)?shù)的高低決出勝負(fù)。352004?2013年NOIP復(fù)賽試題集（提高組）由于求勝心切，小城找督了善于編程的你，讓你幫他求出，對(duì)于給定的靶形數(shù)獨(dú)，能夠得到的最高分?jǐn)?shù)?！据斎搿枯斎胛募麨閟udoku.in。一共9行，每行9個(gè)整數(shù)（每個(gè)數(shù)都在0—9的范圍內(nèi)），表示一個(gè)尚未填滿的數(shù)獨(dú)方格，未填滿的空格用“0”表示。每兩個(gè)數(shù)字之間用一個(gè)空格隔開?！据敵觥枯敵鑫募udoku.out共1行。輸出可以得到的靶形數(shù)獨(dú)的最高分?jǐn)?shù)。如果這個(gè)數(shù)獨(dú)無解，則輸出整數(shù)-1。【輸入輸出樣例1】sudoku.inSudoku.out7009000012829100005900000200080005020003000000648413000000007002090201060804080504012【輸入輸出樣例2】sudoku.inSudoku.out0007024532852900008000740005010195080000070000025030579108000601000060900001000000006【數(shù)據(jù)范圍】40%的數(shù)據(jù)，數(shù)獨(dú)中非0數(shù)的個(gè)數(shù)不少于30。80%的數(shù)據(jù)，數(shù)獨(dú)中非0數(shù)的個(gè)數(shù)不少于26。100%的數(shù)據(jù)，數(shù)獨(dú)中非0數(shù)的個(gè)數(shù)不少于24。362004?2013年NOIP復(fù)賽試題集（提高組）第十六屆全國信息學(xué)奧林匹克分區(qū)聯(lián)賽（NOIP2010）復(fù)賽試題（提高組競賽用時(shí)：3小時(shí)）1、機(jī)器翻譯（translate.pas/c/cpp）【問題描述】小晨的電腦上安裝了一個(gè)機(jī)器翻譯軟件，他經(jīng)常用這個(gè)軟件來翻譯英語文章。這個(gè)翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個(gè)英文單詞用對(duì)應(yīng)的中文含義來替換。對(duì)于每個(gè)英文單詞，軟件會(huì)先在內(nèi)存中查找這個(gè)單詞的中文含義，如果內(nèi)存中有，軟件就會(huì)用它進(jìn)行翻譯；如果內(nèi)存中沒有，軟件就會(huì)在外存中的詞典內(nèi)查找，查出單詞的中文含義然后翻譯，并將這個(gè)單詞和譯義放入內(nèi)存，以備后續(xù)的查找和翻譯。假設(shè)內(nèi)存中有M個(gè)單元，每單元能存放一個(gè)單詞和譯義。每當(dāng)軟件將一個(gè)新單詞存入內(nèi)存前，如果當(dāng)前內(nèi)存中已存入的單詞數(shù)不超過M?1，軟件會(huì)將新單詞存入一個(gè)未使用的內(nèi)存單元；若內(nèi)存中已存入M個(gè)單詞，軟件會(huì)清空最早進(jìn)入內(nèi)存的那個(gè)單詞，騰出單元來，存放新單詞。假設(shè)一篇英語文章的長度為N個(gè)單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設(shè)在翻譯開始前，內(nèi)存中沒有任何單詞?！据斎搿枯斎胛募麨?成1凱04，輸入文件共2行。每行中兩個(gè)數(shù)之間用一個(gè)空格隔開。第一行為兩個(gè)正整數(shù)M和N，代表內(nèi)存容量和文章的長度。第二行為N個(gè)非負(fù)整數(shù)，按照文章的順序，每個(gè)數(shù)（大小不超過1000）代表一個(gè)英文單詞。文章中兩個(gè)單詞是同一個(gè)單詞，當(dāng)且僅當(dāng)它們對(duì)應(yīng)的非負(fù)整數(shù)相同。【輸出】輸出文件translate.out共1行，包含一個(gè)整數(shù)，為軟件需要查詞典的次數(shù)?！据斎胼敵鰳永?】371215441輸出5【輸入輸出樣例1說明】整個(gè)查字典過程如下：每行表示一個(gè)單詞的翻譯，冒號(hào)前為本次翻譯后的內(nèi)存狀況：空：內(nèi)存初始狀態(tài)為空。1：查找單詞1并調(diào)入內(nèi)存。12：查找單詞2并調(diào)入內(nèi)存。12：在內(nèi)存中找到單詞1。125：查找單詞5并調(diào)入內(nèi)存。254：查找單詞4并調(diào)入內(nèi)存替代單詞1。254：在內(nèi)存中找到單詞4。541：查找單詞1并調(diào)入內(nèi)存替代單詞2。共計(jì)查了5次詞典。37

20042004?2013年NOIP復(fù)賽試題集（提高組）【輸入輸出樣例2】ranslate.out210882411781178117882646【數(shù)據(jù)范圍】對(duì)于10%的數(shù)據(jù)有M=1,NW5。對(duì)于100%的數(shù)據(jù)有0<MW100,0<NW1000。38382004?2013年NOIP復(fù)賽試題集（提高組）2、烏龜棋（tortoise.pas/c/cpp）【問題描述】小明過生日的時(shí)候，爸爸送給他一副烏龜棋當(dāng)作禮物。烏龜棋的棋盤是一行N個(gè)格子，每個(gè)格子上一個(gè)分?jǐn)?shù)（非負(fù)整數(shù)）。棋盤第1格是唯一的起點(diǎn)，第N格是終點(diǎn)，游戲要求玩家控制一個(gè)烏龜棋子從起點(diǎn)出發(fā)走到終點(diǎn)。 ……12345……N烏龜棋中M張爬行卡片，分成4種不同的類型（乂張卡片中不一定包含所有4種類型的卡片，見樣例），每種類型的卡片上分別標(biāo)有1、2、3、4四個(gè)數(shù)字之一，表示使用這種卡片后，烏龜棋子將向前爬行相應(yīng)的格子數(shù)。游戲中，玩家每次需要從所有的爬行卡片中選擇一張之前沒有使用過的爬行卡片，控制烏龜棋子前進(jìn)相應(yīng)的格子數(shù)，每張卡片只能使用一次。游戲中，烏龜棋子自動(dòng)獲得起點(diǎn)格子的分?jǐn)?shù)，并且在后續(xù)的爬行中每到達(dá)一個(gè)格子，就得到該格子相應(yīng)的分?jǐn)?shù)。玩家最終游戲得分就是烏龜棋子從起點(diǎn)到終點(diǎn)過程中到過的所有格子的分?jǐn)?shù)總和。很明顯，用不同的爬行卡片使用順序會(huì)使得最終游戲的得分不同，小明想要找到一種卡片使用順序使得最終游戲得分最多?，F(xiàn)在，告訴你棋盤上每個(gè)格子的分?jǐn)?shù)和所有的爬行卡片，你能告訴小明，他最多能得到多少分嗎？【輸入】輸入文件名tortoise.in。輸入文件的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開。第1行2個(gè)正整數(shù)N和M，分別表示棋盤格子數(shù)和爬行卡片數(shù)。第2行N個(gè)非負(fù)整數(shù)，a1,a2,……,aN，其中ai表示棋盤第i個(gè)格子上的分?jǐn)?shù)。第3行M個(gè)整數(shù)，b1,b2,……,bM，表示M張爬行卡片上的數(shù)字。輸入數(shù)據(jù)保證到達(dá)終點(diǎn)時(shí)剛好用光M張爬行卡片，即N?1=EMib1o【輸出】輸出文件名tortoise.outo輸出只有1行，1個(gè)整數(shù)，表示小明最多能得到的分?jǐn)?shù)?！据斎胼敵鰳永?】ortoise.out9561014288185171312173【輸入輸出樣例1說明】小明使用爬行卡片順序?yàn)?,1,3,1,2,得到的分?jǐn)?shù)為6+10+14+8+18+17=73。注意，由于起點(diǎn)是1,所以自動(dòng)獲得第1格的分?jǐn)?shù)6o【輸入輸出樣例2】ortoise.out13849610645513945352489830392004?2013年NOIP復(fù)賽試題集（提高組）11111241455【數(shù)據(jù)范圍】對(duì)于30%的數(shù)據(jù)有1WNW30,1WMW12。對(duì)于50%的數(shù)據(jù)有1WNW120,1WMW50,且4種爬行卡片，每種卡片的張數(shù)不會(huì)超過20。對(duì)于100%的數(shù)據(jù)有1WNW350,1WMW120,且4種爬行卡片，每種卡片的張數(shù)不會(huì)超過40；0WaiW100,1WiWN；1WbiW4,1WiWM。輸入數(shù)據(jù)保證N?1=￡Mib1。402004?2013年NOIP復(fù)賽試題集（提高組）3、關(guān)押罪犯（prison.pas/c/cpp）【問題描述】S城現(xiàn)有兩座監(jiān)獄，一共關(guān)押著N名罪犯，編號(hào)分別為1?N。他們之間的關(guān)系自然也極不和諧。很多罪犯之間甚至積怨已久，如果客觀條件具備則隨時(shí)可能爆發(fā)沖突。我們用“怨氣值”（一個(gè)正整數(shù)值）來表示某兩名罪犯之間的仇恨程度，怨氣值越大，則這兩名罪犯之間的積怨越多。如果兩名怨氣值為c的罪犯被關(guān)押在同一監(jiān)獄，他們倆之間會(huì)發(fā)生摩擦，并造成影響力為c的沖突事件。每年年末，警察局會(huì)將本年內(nèi)監(jiān)獄中的所有沖突事件按影響力從大到小排成一個(gè)列表，然后上報(bào)到S城Z市長那里。公務(wù)繁忙的Z市長只會(huì)去看列表中的第一個(gè)事件的影響力，如果影響很壞，他就會(huì)考慮撤換警察局長。在詳細(xì)考察了N名罪犯間的矛盾關(guān)系后，警察局長覺得壓力巨大。他準(zhǔn)備將罪犯們?cè)趦勺O(jiān)獄內(nèi)重新分配，以求產(chǎn)生的沖突事件影響力都較小，從而保住自己的烏紗帽。假設(shè)只要處于同一監(jiān)獄內(nèi)的某兩個(gè)罪犯間有仇恨，那么他們一定會(huì)在每年的某個(gè)時(shí)候發(fā)生摩擦。那么，應(yīng)如何分配罪犯，才能使Z市長看到的那個(gè)沖突事件的影響力最??？這個(gè)最小值是多少？【輸入】輸入文件名為prison.in。輸入文件的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開。第一行為兩個(gè)正整數(shù)N和M，分別表示罪犯的數(shù)目以及存在仇恨的罪犯對(duì)數(shù)。接下來的M行每行為三個(gè)正整數(shù)aj，bj，cj，表示aj號(hào)和bj號(hào)罪犯之間存在仇恨，其怨氣值為cj。數(shù)據(jù)保證NbajjW<W1,000,000,000,10W<jc，且每對(duì)罪犯組合只出現(xiàn)一次?！据敵觥枯敵鑫募rison.out共1行