北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 更多競(jìng)賽真題免費(fèi)下載 見(jiàn)北京清北學(xué)堂官方網(wǎng)站 學(xué)習(xí)資源：自主招生 學(xué)科競(jìng)賽 高考等資源 第十二屆全國(guó)青少年信息學(xué)奧林匹克 聯(lián)賽復(fù)賽試題 （ NOIP2006 普及組） 競(jìng)賽時(shí)間： 2006 年 11 月 18 日 下午 1:30-4:30 試題名稱 random happy count sequence 目錄 random happy count sequence 輸入文件名 random.in happy.in count.in sequence.in 輸出文件名 random.out happy.out count.out sequence.out 試題類型 非交互式程序題 非交互式程序題 非交 互式程序題 非交互式程序題 附加文件 無(wú) 無(wú) 無(wú) 無(wú) 時(shí)限 1 秒 1 秒 1 秒 1 秒 關(guān)于競(jìng)賽中不同語(yǔ)言使用限制的說(shuō)明 一 關(guān)于使用 Pascal 語(yǔ)言 與 編譯結(jié)果的說(shuō)明 1 對(duì)于 Pascal 語(yǔ)言的程序，當(dāng)使用 IDE 和 fpc 編譯結(jié)果不一致時(shí)，以 fpc 的編譯結(jié)果為準(zhǔn)。 2允許 使用數(shù)學(xué)庫(kù) (uses math 子句 )，以及 ansistring。 但不允許使用編譯開(kāi)關(guān)（ 最后測(cè)試時(shí) pascal的范圍檢查開(kāi)關(guān)默認(rèn)關(guān)閉： $R-,Q-,S-），也不支持與優(yōu)化相 關(guān)的選項(xiàng) 。 二 關(guān)于 C+語(yǔ)言中模板使用的限制說(shuō)明 1 允許使用 的部分 ： 標(biāo)準(zhǔn)容器中的布爾集合，迭代器，串，流。 相關(guān)的頭文件： 2 禁止使用的部分 ： 序列： vector， list， deque 序列適配器： stack, queue, priority_queue 關(guān)聯(lián)容器： map, multimap, set, multiset 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 擬容器： valarray 散列容器： hash_map, hash_set, hash_multimap, hash_multiset 所有的標(biāo)準(zhǔn)庫(kù)算法 相關(guān)頭文件： 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 1.明明的隨機(jī)數(shù) （ random.pas/c/cpp） 【問(wèn)題描述】 明明想在學(xué)校中請(qǐng)一些同學(xué)一起做一項(xiàng)問(wèn)卷調(diào)查，為了實(shí)驗(yàn)的客觀性，他先用計(jì)算機(jī)生成了 N個(gè) 1 到 1000 之間的隨機(jī)整數(shù)（ N 100），對(duì)于其中重復(fù)的數(shù)字，只保留一個(gè)，把其余相同的數(shù)去掉，不同的數(shù)對(duì)應(yīng)著不同的學(xué)生的學(xué)號(hào)。然后再把這些數(shù)從小到大排序，按 照 排好的順序去找同學(xué)做調(diào)查 。請(qǐng)你協(xié)助明明完成“去重”與“排序”的工作。 【輸入文件】 輸入文件 random.in 有 2 行，第 1 行為 1 個(gè)正整數(shù)，表示所生成的隨機(jī)數(shù)的個(gè)數(shù)： N 第 2 行有 N個(gè)用空格隔開(kāi)的正整數(shù)，為所產(chǎn)生的隨機(jī)數(shù)。 【輸出文件】 輸出文件 random.out 也是 2 行，第 1 行為 1個(gè)正整數(shù) M，表示不相同的隨機(jī)數(shù)的個(gè)數(shù)。第 2行為 M 個(gè)用空格隔開(kāi)的正整數(shù)，為從小到大排好序的不相同的隨機(jī)數(shù)。 【輸入樣例】 10 20 40 32 67 40 20 89 300 400 15 【輸出樣例】 8 15 20 32 40 67 89 300 400 2.開(kāi)心的金明 (happy.pas/c/cpp) 【問(wèn)題描述】 金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說(shuō)：“你的房間需要購(gòu)買哪些物品，怎么布置，你說(shuō)了算，只要不超過(guò) N 元錢就行”。今天一早金明就開(kāi)始做預(yù)算 ，但是他想買的東西太多了，肯定會(huì)超過(guò)媽媽限定的 N 元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為 5 等：用整數(shù) 15 表示，第 5 等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是整數(shù)元）。他希望在不超過(guò) N 元 （可以等于 N 元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。 設(shè)第 j 件物品的價(jià)格為 vj，重要度為 wj，共選中了 k件物品，編號(hào)依次為 j1， j2，jk，則所求的總和為： vj1*wj1+vj2*wj2+ +vjk*wjk。（其中 *為乘號(hào)） 請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單。 【輸入文件】 輸入文件 happy.in 的第 1 行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)： N m 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 （其中 N（ 30000）表示總錢數(shù)， m（ 25）為希望購(gòu)買物品的個(gè)數(shù)。） 從第 2 行到第 m+1 行，第 j 行給出了編號(hào)為 j-1 的物品的基本數(shù)據(jù)，每行有 2 個(gè)非負(fù)整數(shù) v p （其中 v 表示該物品的價(jià)格 (v=10000)， p 表示該物品的重要度 (15)） 【輸出文件】 輸出文件 happy.out 只有一個(gè)正整數(shù)，為不超過(guò)總錢數(shù)的物品的價(jià)格與重要度乘積的總和的最大值（ 100000000）。 【輸入樣例】 1000 5 800 2 400 5 300 5 400 3 200 2 【輸出樣例】 3900 3.Jam 的計(jì)數(shù)法 （ count.pas/c/cpp） 【問(wèn)題描述】 Jam 是個(gè)喜歡標(biāo)新立異的科學(xué)怪人。他不使用阿拉伯?dāng)?shù)字計(jì)數(shù)，而是使用小寫(xiě)英文字母計(jì)數(shù)，他覺(jué)得這樣做，會(huì)使世界更加豐富多彩。在他的計(jì)數(shù)法中，每個(gè)數(shù)字的位數(shù)都是相同的（使用相同個(gè)數(shù)的字母），英文字母按原先的順序，排在前面的字母小于排在它后面的字母。我們把這樣的“數(shù)字”稱為 Jam 數(shù)字。在 Jam 數(shù)字中，每個(gè)字母互不相同，而且從左到右是嚴(yán)格遞增的。每次， Jam還指定使用字母的范圍，例如，從 2 到 10，表示只能使用 b,c,d,e,f,g,h,i,j這些字母。如果再規(guī)定位數(shù)為 5，那么，緊接在 Jam 數(shù)字“ bdfij”之后的數(shù)字應(yīng)該是“ bdghi”。（如果我們用U、 V 依次表示 Jam 數(shù)字“ bdfij”與“ bdghi”，則 UV，且不存在 Jam 數(shù)字 P，使 UPV）。你的任務(wù)是：對(duì)于從文件讀入的一個(gè) Jam 數(shù)字，按順序輸出緊接在后面的 5 個(gè) Jam 數(shù)字，如果后面沒(méi)有那么多 Jam 數(shù)字，那么有幾個(gè)就輸出幾個(gè)。 【輸入文件】 輸入文件 counting.in 有 2 行，第 1 行為 3個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)： s t w （其中 s 為所使用的最小的字母的序號(hào)， t 為所使用的最大的字母的序號(hào)。 w 為數(shù)字的位數(shù)，這3 個(gè)數(shù)滿足： 1 st 26, 2 w t-s ） 第 2 行為具有 w 個(gè)小寫(xiě)字母的字符串，為一個(gè)符合要求的 Jam 數(shù)字。 所給的數(shù)據(jù)都是正確的，不必驗(yàn)證。 【輸出文件】 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 輸出文件 counting.out 最多為 5 行，為緊接在輸入的 Jam 數(shù)字后面的 5 個(gè) Jam數(shù)字，如果后面沒(méi)有那么多 Jam 數(shù)字，那么有幾個(gè)就輸出幾個(gè)。每行只輸出一個(gè) Jam 數(shù)字，是由 w 個(gè)小寫(xiě)字母組成的字符串，不要有多余的空格。 【輸入樣例】 2 10 5 bdfij 【輸出樣例】 bdghi bdghj bdgij bdhij befgh 4.數(shù)列 （ sequence.pas/c/cpp） 【問(wèn)題描述】 給定一個(gè)正整數(shù) k(3 k 15),把所有 k 的方冪及所有有限個(gè)互不相等的 k 的方冪之和構(gòu)成一個(gè)遞增的序列，例如，當(dāng) k=3 時(shí)，這個(gè)序列是： 1， 3， 4， 9， 10， 12， 13， （該序列實(shí)際上就是： 30， 31， 30+31， 32， 30+32， 31+32， 30+31+32，） 請(qǐng)你求出這個(gè)序列的第 N 項(xiàng)的值（用 10 進(jìn)制數(shù)表示）。 例如，對(duì)于 k=3， N=100，正確答案應(yīng)該是 981。 【輸入文件】 輸入文件