1、提示：文檔已分節(jié)，可用 word 跳轉(zhuǎn)節(jié)功能 本文為本人將 1995-2008 年歷屆 NOIP 試題、研究成果整理而成，由于“年代久遠(yuǎn)”所以 有不少資料沒有找到。但本人都盡量整理最有價值的信息記錄于此。 資料來源皆為網(wǎng)絡(luò)，若引用請注明出處 一不注意就 208 頁了呢 其實最初只是想方便自己，看著一下午的成果，就忍不住放到了 網(wǎng)絡(luò)上。由于趕時間，質(zhì)量不太好，而且歷屆 NOIP 的排版也不一樣，只是做了粗略的整 理、排版，若有錯誤之處，敬請諒解。 回首歷屆 NOIP，甚至比我自己出生的還早的老題，一代代 OIer 就從這條路上走過，作為 一個不大努力的 OIer，我甚至為自己感到愧疚。總之，為了

2、報答一代代出題人、教師、主 辦方以及 OIer 們，在努力一把也不遲啊。 By 2014 年 8 月 15 日（農(nóng)歷二一四年七月二十）星期五 東營市勝利一中 梅如歌 OI95 “同創(chuàng)杯同創(chuàng)杯”全國青少年信息學(xué)（計算機(jī)）奧林匹克競賽全國青少年信息學(xué)（計算機(jī)）奧林匹克競賽 分區(qū)聯(lián)賽復(fù)賽試題（初中組）分區(qū)聯(lián)賽復(fù)賽試題（初中組） （上機(jī)編程，完成時間：（上機(jī)編程，完成時間：210 分鐘）分鐘） 設(shè)有下列的算式： 8 0 9 - ) - - 1 求出中的數(shù)字，并打印出完整的算式來。 方陣填數(shù)方陣填數(shù)：在一個 NN 的方陣中，填入 1，2，NN 個數(shù)，并要求構(gòu)成如下的 格式： 例： 若將一個正整數(shù)化為二進(jìn)

3、制數(shù)，在此二進(jìn)制數(shù)中，我們將數(shù)字 1 的個數(shù)多于數(shù)字 0 的 個數(shù)的這類二進(jìn)制數(shù)稱為 A 類數(shù)，否則就稱其為 B 類數(shù)。 例如：（13）10=（1101）2 其中 1 的個數(shù)為 3，0 的個數(shù)為 1，則稱此數(shù)為 A 類數(shù)； （10）10=（1010）2 其中 1 的個數(shù)為 2，0 的個數(shù)也為 2，稱此數(shù)為 B 類數(shù)； （24）10=（11000）2 其中 1 的個數(shù)為 2，0 的個數(shù)為 3，則稱此數(shù)為 B 類數(shù)； 程序要求：求出 11000 之中（包括 1 與 1000） ，全部 A、B 兩類數(shù)的個數(shù)。 編碼問題：編碼問題：設(shè)有一個數(shù)組 A:ARRAY0.N-1 OF INTEGER；數(shù)組中存

4、放的元素為 0N-1 之間的整數(shù)，且 AiAj（當(dāng) ij 時） 。 例如：N=6 時，有： A=（4，3，0，5，1，2） 此時，數(shù)組 A 的編碼定義如下： A0的編碼為 0； N=5 13 14 15 16 1 12 23 24 17 2 11 22 25 18 3 10 21 20 19 4 9 8 7 6 5 N=6 16 17 18 19 20 1 15 30 31 32 21 2 14 29 36 33 22 3 13 28 35 34 23 4 12 27 26 25 24 5 11 10 9 8 7 6 Ai的編碼為：在 A0，A1，Ai-1中比 Ai的值小的個數(shù)（i=1，2N-

5、 1） 上面數(shù)組 A 的編碼為：B=（0，0，0，3，1，2） 程序要求解決以下問題：程序要求解決以下問題： 給出數(shù)組 A 后，求出其編碼； 給出數(shù)組 A 的編碼后，求出 A 中的原數(shù)據(jù)。 燈的排列問題：燈的排列問題：設(shè)在一排上有 N 個格子（N20） ，若在格子中放置有不同顏色的燈， 每種燈的個數(shù)記為 N1，N2，Nk（k 表示不同顏色燈的個數(shù)） 。 放燈時要遵守下列規(guī)則：放燈時要遵守下列規(guī)則： 同一種顏色的燈不能分開； 不同顏色的燈之間至少要有一個空位置。 例如：N=8（格子數(shù)） R=2（紅燈數(shù)） B=3（藍(lán)燈數(shù)） 放置的方法有： R-B 順序 RRBBB RRBBB RRBBB RRBB

6、B RRBBB RRBBB B-R 順序 BBBRR BBBRR BBBRR BBBRR BBBRR BBBRR 放置的總數(shù)為 12 種。 數(shù)據(jù)輸入的方式為： N P1（顏色，為一個字母） N1（燈的數(shù)量） P2 N2 Q（結(jié)束標(biāo)記，Q 本身不是燈的顏色） 程序要求：程序要求：求出一種順序的排列方案及排列總數(shù)。 NOI95 “同創(chuàng)杯同創(chuàng)杯”全國青少年信息學(xué)（計算機(jī)）奧林匹克競賽全國青少年信息學(xué)（計算機(jī)）奧林匹克競賽 分區(qū)聯(lián)賽復(fù)賽測試數(shù)據(jù)（初中組）分區(qū)聯(lián)賽復(fù)賽測試數(shù)據(jù)（初中組） 正確算式如下：8 分 809 打印格式占 4% 9709 算式不對不給分 96 109 108 1 本題 18 分（4

7、%+6%+8%） 輸入 N=1 （4%） 輸入 N=3 （6%） 結(jié)果： 結(jié)果： 17 8 1 6 9 2 5 4 3 輸入 N=10（8%） 結(jié)果： 28 29 30 31 32 33 34 35 36 1 27 58 59 60 61 62 63 64 37 2 26 57 80 81 82 83 84 65 38 3 25 56 79 94 95 96 85 66 39 4 24 55 78 93 100 97 86 67 40 5 23 54 77 92 99 98 87 68 41 6 22 53 76 91 90 89 88 69 42 7 21 52 75 74 73 72 71

8、 70 43 8 20 51 50 49 48 47 46 45 44 9 1918 17 16 15 14 13 12 11 10 本題 14 分 輸出結(jié)果為： A 類=538 B 類=462 本題 30 分（15%+15%） 由數(shù)組求編碼：共 15 分（5%+5%+5%） a 輸入：N=6 A=（0，1，2，3，4，5） 輸出： B=（0，1，2，3，4，5） 12） b 輸入：N=6 A=（5，4，3，2，1，0） 輸出： B=（0，0，0，0，0，0） c 輸入：N=8 A=（1，0，3，2，5，4，7，6） 輸出： B=（0，0，2，2，4，4，6，6） 由編碼求原數(shù)組：共 15 分

9、（5%+5%+5%） a 輸入：N=5 B=（0，0，0，0，0） 輸出： A=（4，3，2，1，0） b 輸入：N=10 B=（0，1，2，3，4，5，6，7，8，9） 輸出： A=（0，1，2，3，4，5，6，7，8，9） c 輸入：N=7 B=（0，0，0，0，4，5，6） 輸出： A=（3，2，1，0，4，5，6） 本題共 30 分（10%+10%+10%） 數(shù)據(jù)輸入： N=6 P1=R N1=1 Q 數(shù)據(jù)輸入：N=6 P1=R N1=2 P2=Y N2=1 Q R R R R R R 排列方案： 排列總數(shù)=6 RRY RRY RRY RRY RRY RRY 排列方案： 排列總數(shù)=12

10、 數(shù)據(jù)輸入：N=12 P1=R N1= 3 P2=B N2=2 P3=Y N3=1 Q RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY 排列方案： 排列總數(shù)：

11、 1052=210 NOI95 “同創(chuàng)杯同創(chuàng)杯”全國青少年信息學(xué)（計算機(jī)）奧林匹克競賽全國青少年信息學(xué)（計算機(jī)）奧林匹克競賽 分區(qū)聯(lián)賽復(fù)賽試題（高中組）分區(qū)聯(lián)賽復(fù)賽試題（高中組） （上機(jī)編程，完成時間：（上機(jī)編程，完成時間：210 分鐘）分鐘） 編碼問題：編碼問題： 設(shè)有一個數(shù)組 A:ARRAY0.N-1 OF INTEGER； 數(shù)組中存放的元素為 0N-1 之間的整數(shù)，且 AiAj（當(dāng) ij 時） 。 例如：N=6 時，有： A=（4，3，0，5，1，2） 此時，數(shù)組 A 的編碼定義如下： A0的編碼為 0； Ai的編碼為：在 A0，A1，Ai-1中比 Ai的值小的個數(shù)（i=1，2，N- 1

12、） 上面數(shù)組 A 的編碼為： B=（0，0，0，3，1，2） 程序要求解決以下問題：程序要求解決以下問題： 給出數(shù)組 A 后，求出其編碼。 給出數(shù)組 A 的編碼后，求出 A 中的原數(shù)據(jù)。 燈的排列問題：燈的排列問題： 設(shè)在一排上有 N 個格子（N20） ，若在格子中放置有不同顏色的燈，每種燈的個數(shù)記 為 N1，N2，Nk（k 表示不同顏色燈的個數(shù)） 。 放燈時要遵守下列規(guī)則：放燈時要遵守下列規(guī)則： 同一種顏色的燈不能分開； 不同顏色的燈之間至少要有一個空位置。 例如：N=8（格子數(shù)） R=2（紅燈數(shù)） B=3（藍(lán)燈數(shù)） 放置的方法有： R-B 順序 RRBBB RRBBB RRBBB RRBB

13、B RRBBB RRBBB B-R 順序 BBBRR BBBRR BBBRR BBBRR BBBRR BBBRR 放置的總數(shù)為 12 種。 數(shù)據(jù)輸入的方式為： N P1（顏色，為一個字母） N1（燈的數(shù)量） P2 N2 Q（結(jié)束標(biāo)記，Q 本身不是燈的顏色） 程序要求：求出一種順序的排列方案及排列總數(shù)。程序要求：求出一種順序的排列方案及排列總數(shù)。 設(shè)有一個四層的積木塊，14 層積木塊的數(shù)量依次為：5，6，7，8 如下圖所示放置： 8158516914 23414326 其中，給出第三層與第四層所標(biāo)示的數(shù)字，并已知第三層的數(shù)據(jù)是由第四層的數(shù)據(jù)計 算出來的。 計算的方法是：第三層的某個數(shù)據(jù) A 是由

14、第四層相鄰的兩個數(shù)據(jù) B，C 經(jīng)過某種計算 后產(chǎn)生的： A BC 計算所用到的計算符為：+，-，且無優(yōu)先級之分（自左向右計算） ，運(yùn)算符最多為 2 個。 如：3+45=35 54+3=23 可以看出，上圖中的第三層的數(shù)據(jù)是由第四層的數(shù)據(jù)用以下計算公式計算出來的： A=BC+B 也就是：8=23+2，15=34+3，14=26+2 程序要求：程序要求： 給出第四層與第三層的數(shù)據(jù)后，將第一、二層的每塊積木標(biāo)上相應(yīng)的數(shù)據(jù)，并輸出整 個完整的積木圖及計算公式。 輸入數(shù)據(jù)不存在出錯的情況，同時也不會超過整數(shù)的范圍。 計算時可允許出現(xiàn)以下情況： A=B （即可理解為運(yùn)算符的個數(shù)為零） A=BB+B （即全

15、部由 B 產(chǎn)生） NOI95 “同創(chuàng)杯同創(chuàng)杯”全國青少年信息學(xué)（計算機(jī)）奧林匹克競賽全國青少年信息學(xué)（計算機(jī)）奧林匹克競賽 分區(qū)聯(lián)賽復(fù)賽測試數(shù)據(jù)（高中組）分區(qū)聯(lián)賽復(fù)賽測試數(shù)據(jù)（高中組） 本題 30 分（15%+15%） 由數(shù)組求編碼：共 15 分（5%+5%+5%） a 輸入：N=6 A=（0，1，2，3，4，5） 輸出編碼： B=（0，1，2，3，4，5） b 輸入：N=6 A=（5，4，3，2，1，0） 輸出編碼： B=（0，0，0，0，0，0） c 輸入：N=8 A=（1，0，3，2，5，4，7，6） 輸出編碼： B=（0，0，2，2，4，4，6，6） 由編碼求原數(shù)組：共 15 分（5%

16、+5%+5%） a 輸入：N=5 B=（0，0，0，0，0） 輸出編碼： A=（4，3，2，1，0） b 輸入：N=10 B=（0，1，2，3，4，5，6，7，8，9） 輸出編碼： A=（0，1，2，3，4，5，6，7，8，9） c 輸入：N=7 B=（0，0，0，0，4，5，6） 輸出編碼： A=（3，2，1，0，4，5，6） 本題共 30 分（10%+10%+10%） 數(shù)據(jù)輸入： N=6 P1=R N1=1 Q 數(shù)據(jù)輸入：N=6 P1=R N1=2 P2=Y N2=1 Q R R R R R R 排列方案： 排列總數(shù)=6 RRY RRY RRY RRY RRY RRY 排列方案： 排列總數(shù)

17、=12 數(shù)據(jù)輸入：N=12 P1=R N1= 3 P2=B N2=2 P3=Y N3=1 Q 本題共 40 分（12%+14%+14%） 輸入3 4 4 4 4 3 4 12 2 2 2 2 1 3 應(yīng)打印出完整的圖形：（12 分） 15 16 16 15 4 7 8 8 8 7 7 3 4 4 4 4 3 4 1 2 2 2 2 2 1 3 公式：A=B+C RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY

18、 RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY RRRBBY 排列方案： 排列總數(shù)： 1052=210 輸入 1 0 1 0 1 0 1 2 1 2 1 2 1 2 1 應(yīng)打印出完整的圖形（14 分） 1 -1 1 -1 1 0 1 0 -1 0 -1 1 0 1 0 1 0 1 2 1 2 1 2 1 2 1 公式：A=BC-C 輸入 2 4 2 4 2 4 2 2 1 2 1 2 1 2 1 應(yīng)打印出

19、完整的圖形：（14 分） 8192 16394 8192 16394 8192 32 16 32 16 32 16 2 4 2 4 2 4 2 2 1 2 1 2 1 2 1 公式：A=BCC 或： 8 16 8 16 8 8 4 8 4 8 4 2 4 2 4 2 4 2 2 1 2 1 2 1 2 1 公式：A=B+B 第二屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第二屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （初中組 競賽用時：3 小時） 1編制一個乘法運(yùn)算的程序（20 分） 從鍵盤讀入 2 個 100 以內(nèi)的正整數(shù)，進(jìn)行乘法運(yùn)算并以豎式輸出。 例如，輸入格式：89

20、13 又如，輸入格式：16 8 輸出格式： 89 輸出格式： 16 13 8 267 128 89 1157 2輸入三個自然數(shù) N，i，j （1=i=N，1=j=N） ，輸出在一個 N*N 格的棋盤中，與格 子（i，j）同行、同列、同一對角線的所有格子的位置。 （20 分） 如：n=4，i=2，j=3 表示了棋盤中的第二行第三列的格子，如下圖： 第一列第二列第三列第四列 (2,3) 當(dāng) n=4，i=2，j=3 時，輸出的結(jié)果是： (2,1) (2,2) (2,3) (2,4) 同一行上格子的位置 (1,3) (2,3) (3,3) (4,3)同列列上格子的位置 (1,2) (2,3) (3,4

21、) 左上到右下對角線上的格子的位置 (4,1) (3,2) (2,3) (1,4) 左下到右上對角線上的格子的位置 3字符串編輯（30 分） 從鍵盤輸入一個字符串（長度=40 個字符） ，并以字符 . 結(jié)束。 例如：This is a book. 現(xiàn)對該字符串進(jìn)行編輯，編輯功能有： D：刪除一個字符，命令的方式為： D a 其中 a 為被刪除的字符 例如：D s 表示刪除字符 s ，若字符串中有多個 s，則刪除第一次出現(xiàn)的。 如上例中刪除的結(jié)果為： Thi is a book. I：插入一個字符，命令的格式為： I a1 a2 其中 a1 表示插入到指定字符前面，a2 表示將要插入的字符。 例

22、如：I s d 表示在指定字符 s 的前面插入字符 d ，若原串中有多個 s ，則 插入在最后一個字符的前面，如上例中： 第 1 行 第 2 行 第 3 行 第 4 行 原 串：This is a book. 插入后：This ids a book. R：替換一個字符，命令格式為： R a1 a2 其中a1 為被替換的字符，a2 為替換的字符，若在原串中有多個a1 則應(yīng) 全部替換。 例如： 原 串： This is a book. 輸入命令：R o e 替換后的字符串為： This is a beek. 在編輯過程中，若出現(xiàn)被改的字符不存在時，則給出提示信息。 4比賽安排（30 分） 設(shè)有有

23、2 n（n=6）個球隊進(jìn)行單循環(huán)比賽，計劃在 2 n 1 天內(nèi)完成，每個隊每天進(jìn)行 一場比賽。設(shè)計一個比賽的安排，使在 2 n 1 天內(nèi)每個隊都與不同的對手比賽。 例如 n=2 時的比賽安排： 隊 1 23 4 比賽 1=23=4 一天 1=32=4 二天 1=4 2=3 三天 第二屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽第二屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽 復(fù)賽參考答案（初中組）復(fù)賽參考答案（初中組） 題號輸入輸出 11 5 2 5 2 10 12 25 40 25 40 00 100 1000 13 87 76 87 76 522 609 6612 14 3 78 3 78

24、 24 21 234 題號輸入輸出 21N=4 i=4 j=1 （4，1） （4，2） （4，3） （4，4） （1，1） （2，1） （3，1） （4，1） （4，1） （4，1） （3，2） （2，3） （1，4） 22N=1 i=1 j=1 （1，1） （1，1） （1，1） （1，1） 23N=5 i=3 j=3 （3，1） （3，2） （3，3） （3，4） （3，5） （1，3） （2，3） （3，3） （4，3） （5，3） （1，1） （2，2） （3，3） （4，4） （5，5） （5，1） （4，2） （3，3） （2，4） （1，5） 24N=6 i=4 （4，1） （4

25、，2） （4，3） （4，4） （4，5） （4，6） j=6（1，6） （2，6） （3，6） （4，6） （5，3） （6，6） （1，3） （2，4） （3，5） （4，6） （6，4） （5，5） （4，6） 題號輸入輸出 31原串：a123 b12 aa. 命令：d 2 a13 b12 aa 32原串：abc dc e . 命令：I c f abc dfc e. 33原串：sssssss. 命令：I s t ssssssts. 34原串：abababab. 命令：d b aababab. 35原串：abcd adc 命令：r d c abcc acc. 36原串：abcd efg.

26、命令：r s t 指定字符不存在信息 37原串：a 命令：r . a aa 38原串：ababababab. 命令：r b a aaaaaaaaaa. 39原串：sssssss ss. 命令：r s t ttttttt tt. 31 0 原串：. 命令：r . % 題號輸入輸出 41n=11-2 42n=21-2，3-4 1-3，2-4 1-4，2-3 43n=31-2，3-4，5-6，7-8 1-3，2-4，5-7，6-8 1-4，2-3，5-8，6-7 1-5，2-6，3-7，4-8 1-6，2-5，3-8，4-7 1-7，2-8，3-5，4-6 1-8，2-7，3-6，4-5 44n=4

27、1-2，3-4，5-6，7-8，9-10， 11-12，13-14，15-16 1-3，2-4，5-7，6-8，9-11， 10-12，13-15，14-16 1-4，2-3，5-8，6-7，9-12， 10-11，13-16，14-15 1-5，2-6，3-7，4-8，9-13， 10-14，11-15，12-16 1-6，2-5，3-8，4-7，9-14， 10-13，11-16，12-15 1-7，2-8，3-5，4-6，9-15， 10-16，11-13，12-14 1-8，2-7，3-6，4-5，9-16， 10-15，11-14，12-13 1-9，2-10，3-11，4-12，

28、5- 13， 6-14，7-15，8-16 1-10，2-9，3-12，4-11，5- 14， 6-13，7-16，8-15 1-11，2-12，3-9，4-10，5- 15， 6-16，7-13，8-14 1-12，2-11，3-10，4-9，5- 16， 6-15，7-14，8-13 1-13，2-14，3-15，4-16，5- 9， 6-10，7-11，8-12 1-14，2-13，3-16，4-15，5- 10， 6-9，7-12,8-11 1-15，2-16，3-13，4-14，5- 11， 6-12，7-9，8-10 1-16，2-15，3-14，4-13，5- 12， 6-11，

29、7-10，8-9 第二屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第二屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （高中組（高中組 競賽用時：競賽用時：3 小時）小時） 1比賽安排（20 分） 設(shè)有有 2 n（n=6）個球隊進(jìn)行單循環(huán)比賽，計劃在 2 n 1 天內(nèi)完成，每個隊每天進(jìn)行 一場比賽。設(shè)計一個比賽的安排，使在 2 n 1 天內(nèi)每個隊都與不同的對手比賽。 例如 n=2 時的比賽安排： 隊 1 23 4 比賽 1=23=4 一天 1=32=4 二天 1=4 2=3 三天 2數(shù)制轉(zhuǎn)換（20 分） 設(shè)有一個字符串 A$的結(jié)構(gòu)為： A$=mp 其中 m 為數(shù)字串（長度=20）

30、 ，而 n,p 均為 1 或 2 位的數(shù)字串（其中所表達(dá)的內(nèi)容在 2-10 之間） 。 程序要求：從鍵盤上讀入 A$后（不用正確性檢查） ，將 A$中的數(shù)字串 m(n 進(jìn)制)，以 p 進(jìn)制的形式輸出。 例如：A$=488 其意義為：將 10 進(jìn)制數(shù) 48，轉(zhuǎn)換成 8 進(jìn)制數(shù)輸出。 輸出結(jié)果為：48=60 4挖地雷（30 分） 在一個地圖上有 N 個地窖（N=20） ，每個地窖中埋有一定數(shù)量的地雷。同時，給出 地窖之間的連接路徑。 例如： 題目要求 當(dāng)?shù)亟鸭捌溥B接的數(shù)據(jù)給出之后，某人可以從任一處開始挖地雷，然后可以沿著指出 的連接往下挖（僅能選擇一條路徑） ，當(dāng)無連接時挖地雷工作結(jié)束。設(shè)計一個挖

31、地雷的方案， 使某人能挖到最多的地雷。 輸入格式： N： （表示地窖的個數(shù)） 1，W2，W3，WN （表示每個地窖中埋藏的地雷數(shù)量） A12 . A1N A23.A2N . AN-1 N 輸出格式： V1 V 2 V3 V4 V5 地窖之間連接路徑（其中ij=1 表示地窖 i,j 之間是否有通路：通 Aij=1,不通 Aij=0） K1-K2-.KV （挖地雷的順序） MAX （挖地雷的數(shù)量） 例如： - - 其輸入格式為： 輸出： 51 3 -4 -5 10，8，4，7，6max=27 1 1 1 0 0 0 0 1 1 1 4砝碼稱重（30 分） 設(shè)有 1g、2g、3g、5g、10g、20

32、g 的砝碼各若干枚（其總重=1000） ， 要求： 輸入方式：a1 a2 a3 a4 a5 a6 （表示 1g 砝碼有 a1 個，2g 砝碼有 a2 個，20g 砝碼有 a6 個） 輸出方式：Total=N （N 表示用這些砝碼能稱出的不同重量的個數(shù)，但不包括一個砝碼也不 用的情況） 如輸入：1_1_0_0_0_0 （注：下劃線表示空格） 輸出：TOTAL=3 表示可以稱出 1g，2g，3g 三種不同的重量。 第二屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽第二屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽 復(fù)賽參考答案（高中組）復(fù)賽參考答案（高中組） 題號輸入輸出 1 1 n=11-2 1 2

33、 n=21-2，3-4 1-3，2-4 1-4，2-3 1 3 n=31-2，3-4，5-6，7-8 1-3，2-4，5-7，6-8 1-4，2-3，5-8，6-7 1-5，2-6，3-7，4-8 1-6，2-5，3-8，4-7 1-7，2-8，3-5，4-6 1-8，2-7，3-6，4-5 1 4 n=41-2，3-4，5-6，7-8，9-10， 11-12，13-14，15-16 1-3，2-4，5-7，6-8，9-11， 10-12，13-15，14-16 1-4，2-3，5-8，6-7，9-12， 10-11，13-16，14-15 1-5，2-6，3-7，4-8，9-13， 10-1

34、4，11-15，12-16 1-6，2-5，3-8，4-7，9-14， 10-13，11-16，12-15 1-7，2-8，3-5，4-6，9-15， 10-16，11-13，12-14 1-8，2-7，3-6，4-5，9-16， 10-15，11-14，12-13 1-9，2-10，3-11，4-12， 5- 13， 6-14，7-15，8-16 1-10，2-9，3-12，4-11，5-14， 6-13，7-16，8-15 1-11，2-12，3-9，4-10，5- 15， 6-16，7-13，8-14 1-12，2-11，3-10，4-9，5- 16， 6-15，7-14，8-13 1-

35、13，2-14，3-15，4-16，5- 9， 6-10，7-11，8-12 1-14，2-13，3-16，4-15，5- 10， 6-9，7-12,8-11 1-15，2-16，3-13，4-14，5- 11， 6-12，7-9，8-10 1-16，2-15，3-14，4-13，5- 12， 6-11，7-10，8-9 題號輸入輸出 2110110101=5 22110121101=10001001101 233704103704=1988 2473873=111 2544844=40 2662562=200 279347934=2503 282216221=501 294437443=23

36、4 21 0 61361=1211 題號輸入輸出 31n=3 w1=10,w2=20,w3=5 0 1 0 2 MAX=20 32n=3 w1=5,w2=10,w3=5 1 1 0 1-2-3 MAX=20 33n=6 w1=5,w2=10,w3=20 w4=5,w5=4,w6=5 1 0 1 0 0 0 1 0 0 1 0 0 1 1 1 3-4-2-1 MAX=40 34n=6 w1=10,w2=15,w3=20 w4=15,w5=5, w6=10 3 MAX=20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 35n=11 w1=10,w2=20,w3=30 w4=15,w

37、5=40, w6=10 w7=20,w8=40, w9=10 w10=5,w11=200 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 11-10-9-7-8-6-2-5-4-3-1 MAX=400 題號輸入輸出 411 1 0 0 0 0Total=3 422 2 0 0 0 0Total=6 431 0 3 0 0 0Total=7 443 4 0 5 0 0Total=36 452 2 2 2 2 2Total=82

38、 460 3 2 7 4 5Total=185 470 6 3 4 2 1Total=79 481 2 3 4 5 6Total=204 486 5 4 3 2 1Total=83 41 0 10 10 10 10 1 1Total=140 第三屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第三屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （初中組（初中組 競賽用時：競賽用時：3 小時）小時） 1設(shè)有一個 n*m 方格的棋盤（1m,n100） 。 （30%） 求出該棋盤中包含多少個正方形、多少個長方形（不包括正方形） 。 例如：當(dāng) n=2，m=3 時 正方形的個數(shù)有 8 個；即邊

39、長為 1 的正方形有 6 個； 邊長為 2 的正方形有 2 個。 長方形的個數(shù)有 10 個； 即 2*1 的長方形有 4 個； 1*2 的長方形有 3 個； 3*1 的長方形有 2 個； 3*2 的長方形有 1 個。 程序要求：輸入：n 和 m 輸出：正方形的個數(shù)與長方形的個數(shù) 如上例：輸入：2 3 輸出：8，10 2將 1，2，,9 共 9 個數(shù)排成下列形態(tài)的三角形。 （30%） a b c d e f g h i 其中：ai 分別表示 1，2，,9 中的一個數(shù)字，并要求同時滿足下列條件： （1）afi; （2）bd, gh, ce （3）a+b+d+f=f+g+h+i=i+e+c+a=P

40、程序要求： 根據(jù)輸入的邊長之和 P 輸出所有滿足上述條件的三角形的個數(shù)以及其中的一種方案。 3設(shè)有一個 NM（l N50， l M 50）的街道（如下圖）：（40%） 規(guī)定行人從 A(1,1)出發(fā)，在街道上只能向東或北方向行走。 如下為 N3，M=3 的街道圖，從 A 出發(fā)到達(dá) B 共有 6 條可供行走的路徑： A6 A7 B（N，M） A3 A4 A5 A A1 A2 若在 NM 的街道中，設(shè)置一個矩形障礙區(qū)域（包括圍住該區(qū)域的街道）不讓行 人通行，如圖中用“”表示的部分。 此矩形障礙區(qū)域用 2 對頂點坐標(biāo)給出,前圖中的 2 對頂點坐標(biāo)為:(2，2),(8，4),此時 從 A 出發(fā)到達(dá) B

41、的路徑僅有兩條。 程序要求： 任務(wù)一：給出 N，M 后，求出所有從 A 出發(fā)到達(dá) B 的路徑的條數(shù)。 任務(wù)二：給出 N，M，同時再給出此街道中的矩形障礙區(qū)域的 2 對頂點坐標(biāo)(X1,y1), （X2，Y2） ，然后求出此種情況下所有從 A 出發(fā)到達(dá) B 的路徑的條數(shù)。 南 * * 東 北 5 4 3 2 1 西 1 2 3 4 5 6 7 8 9 A（1，1） 1.A-A1-A2-A5-B 2. A-A1-A4-A5-B 3. A-A1-A4-A7-B 4. A-A3-A4-A5-B 5. A-A3-A4-A7-B 6. A-A3-A6-A7-B B（9，5 ） 第三屆全國青少年信息學(xué)（計算機(jī)

42、）奧林匹克分區(qū)聯(lián)賽第三屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽 復(fù)賽參考答案（初中組）復(fù)賽參考答案（初中組） 題一輸入輸出 11N=1，M=11，0 12N=2，M=25，4 13N=10，M=10385，2640 14N=20，M=204970，92680 15N=50，M=5042925，1582700 題二輸入輸出 21P=23滿足條件的方案數(shù)：2（如下） 7 7 3 1 2 3 5 6 6 4 8 2 4 9 8 1 5 9 22P=18無解 23P=19滿足條件的方案數(shù)：4（如下） 1 1 5 3 6 2 9 8 8 9 4 2 6 7 4 3 5 7 2 2 5 4 6 1 9

43、 6 8 9 3 1 8 7 3 4 5 7 24P=20滿足條件的方案數(shù)：6（如下） 1 2 6 3 6 1 8 7 7 9 5 2 4 9 5 3 4 8 3 2 4 1 7 4 8 9 3 9 5 2 6 7 8 6 1 5 4 4 3 1 2 3 8 9 9 7 5 2 7 6 5 1 8 6 題三任 務(wù) 一 31N=2，M=22 32N=10，M=1048620 33N=50，M=5058，980，856，902，730，428，6 00 任 務(wù) 二 34N=30，M=40 （5，5） ， （15，15） 118，200946，737，728，400 35N=50，M=50 （2，2

44、） ， （49，49） 2 36N=50，M=50 （2，2） ， （7，5） 36，014，973，809，750，037，8 00 第三屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第三屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （高中組（高中組 競賽用時：競賽用時：3 小時）小時） 1在 N*N 的棋盤上（1N10） ，填入 1，2，N*N 共 N*N 個數(shù)，使得任意兩個相 鄰的數(shù)之和為素數(shù)。 （30%） 例如：當(dāng) N=2 時，有： 12 43 當(dāng) N=4 時，一種可以填寫的方案如下： 121112 161585 134914 67103 在這里我們約定：左上角的格子里必

45、須填數(shù)字 1。 程序要求： 輸入：N； 輸出：如有多種解，則輸出第一行、第一列之和為最小的排列方案；若無解，則 輸出“NO！” 。 2代數(shù)表達(dá)式的定義如下： 例如，下面的式子是合法的代數(shù)表達(dá)式： a； 其相鄰數(shù)的和為素數(shù)的有： 1+2，1+4，4+3，2+3 a c b 字母 a+b*(a+c); a*a/(b+c) 下面的式子是不合法的代數(shù)表達(dá)式： ab; a+a*/(b+c); 程序要求： 輸入：輸入一個字符串，以“；”結(jié)束， “；”本身不是代數(shù)表達(dá)式中字符，僅作 為結(jié)束） ； 輸出：若表達(dá)式正確，則輸出“OK” ；若表達(dá)式不正確，則輸出“ERROR” ，及 錯誤類型。 錯誤類型約定： 1

46、式了中出現(xiàn)不允許的字符； 2括號不配對； 3其它錯誤。 例如：輸入：a+(b); 輸出：OK 例如：輸入：a+(b+c*a; 輸出：ERROR 2 3騎士游歷： 設(shè)有一個 n*m 的棋盤（2n50，2m50） ，如下圖，在棋盤上左下角有一個中國 象棋馬。 （n,m） (1,1) 馬走的規(guī)則為： （1）馬走日字； （2）馬只能向右走 即如下圖如示： 任務(wù) 1：當(dāng) n,m 輸入之后，找出一條從左下角到右上角的路徑。 例如，輸入：n=4，m=4 馬 (4,4) (1,1) 輸出：路徑的格式：(1,1)(2,3)(4,4)。若不存在路徑，則輸出 NO 任務(wù) 2：當(dāng) n，m 給出之后，同時給出馬起點的位

47、置和終點的位置，試找出從起點到 終點的所有路徑的數(shù)目。 例如：（n=10,m=10） ， （1，5） （起點） ， （3，5） （終點） 輸 出：2（即由（1，5）到（3，5）共有 2 條路徑） 輸入格式：n,m,x1,y1,x2,y2 (分別表示 n,m,起點坐標(biāo)，終點坐標(biāo)) 輸出格式：路徑數(shù)目（若不存在從起點到終點的路徑，輸出 0） 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 第三屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽第三屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽 復(fù)賽測試數(shù)據(jù)（高中組）復(fù)賽測試數(shù)據(jù)（高中組） 題號輸入輸出 11N=1NO 1

48、2N=2 1 2 4 3 13N=3NO 14N=4 1 2 11 12 1 2 11 12 4 15 8 5 4 9 8 5 7 16 3 14 7 10 3 14 6 13 10 9 6 13 16 15 15N=5 1 2 3 4 7 1 2 3 4 7 6 5 14 15 16 6 5 14 15 16 13 24 23 8 21 13 24 23 8 21 10 19 18 11 20 10 19 18 11 20 9 22 25 12 17 9 22 25 12 17 題號輸入輸出 21a+xError 1 22(b+c)Ok 23a+b(c+a)Error 3 24(a+(b+c

49、)Error 2 25a+)b+c(Error 2 題號任 務(wù) 一 31N=9，M=5（1，1）-（3，2）-（5，1） （6，3） -（7，1）-（8，3）-（9，5） （答案不唯一） 32N=3，M=3NO 任 務(wù) 二 33N=30，M=30 （1，15） ， （3，15） 2 34N=30，M=30 （1，15） ， （5，15） 8 35N=30，M=30 （1，15） ， （10，15） 460 36N=50，M=503，323，759，302，857，476 （1，25） ， （40，25） 第四屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第四屆全國青少年信息學(xué)（計算機(jī)）奧

50、林匹克分區(qū)聯(lián)賽復(fù)賽試題 （初中組上機(jī)編程（初中組上機(jī)編程 競賽用時：競賽用時：3 小時）小時） 1將 1，2，9 共 9 個數(shù)分成三組，分別組成三個三位數(shù)，且使這三個三位數(shù)構(gòu)成 1：2：3 的比例，試求出所有滿足條件的三個三位數(shù)。 例如：三個三位數(shù) 192，384，576 滿足以上條件。 30% 2用高精度計算出 S=1！+2！+3！+n！（n50） 其中“！”表示階乘，例如：5！=5*4*3*2*1。 輸入正整數(shù) N，輸出計算結(jié)果 S。 30% 3任何一個正整數(shù)都可以用 2 的冪次方表示。例如： 40% 137=27+23+20 同時約定方次用括號來表示，即 ab 可表示為 a（b） 。 由

51、此可知，137 可表示為： 2（7）+2（3）+2（0） 進(jìn)一步：7= 22+2+20 （21用 2 表示） 3=2+20 所以最后 137 可表示為： 2（2（2）+2+2（0） ）+2（2+2（0） ）+2（0） 又如： 1315=210 +28 +25 +2+1 所以 1315 最后可表示為： 2（2（2+2（0） ）+2）+2（2（2+2（0） ） ）+2（2（2）+2（0） ）+2+2（0） 輸入：正整數(shù)（n20000） 輸出：符合約定的 n 的 0，2 表示（在表示中不能有空格） 第四屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽第四屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽 復(fù)賽

52、參考答案（初中組）復(fù)賽參考答案（初中組） 題號輸入輸出分值 1.1無192 384 576 219 438 657 273 546 819 327 654 981(共四組) 30 分 2.1N=68735 分 2.2N=104,037,9135 分 2.3N=221,177,652 ,997,443 ,428,940 31310 分 2.4N=4812,678,163,798,554,051,767,172,643,373,255, 731,925,167,694,226,950,680,420,940,313 10 分 3.1732(2(2)+2)+2(2+2(0)+2(0)5 分 3.21

53、362(2(2)+2+2(0)+2(2+2(0)5 分 3.32552(2(2)+2+2(0)+2(2(2)+2)+2(2(2)+2(0)+2(2(2)+2(2+2(0) +2(2)+2+2(0) 10 分 3.413842(2(2+2(0)+2)+2(2(2+2(0)+2(2(2)+2)+2(2(2)+2(0)+2(2 +2(0) 10 分 3.5163852(2(2+2(0)+2(2)+2)+2(0)10 分 第四屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第四屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （高中組（高中組 競賽用時：競賽用時：3 小時）小時） 1火車從始發(fā)

54、站（稱為第 1 站）開出，在始發(fā)站上車的人數(shù)為 a，然后到達(dá)第 2 站，在第 2 站有人上、下車，但上、下車的人數(shù)相同，因此在第 2 站開出時（即在到達(dá)第 3 站之 前）車上的人數(shù)保持為 a 人。從第 3 站起（包括第 3 站）上、下車的人數(shù)有一定規(guī)律： 上車的人數(shù)都是前兩站上車人數(shù)之和，而下車人數(shù)等于上一站上車人數(shù)，一直到終點站 的前一站（第 n-1 站） ，都滿足此規(guī)律。現(xiàn)給出的條件是：共有 N 個車站，始發(fā)站上車 的人數(shù)為 a，最后一站下車的人數(shù)是 m（全部下車） 。試問 x 站開出時車上的人數(shù)是多 少？ 輸入：a，n，m 和 x 輸出：從 x 站開出時車上的人數(shù)。 20% 2設(shè)有 n

55、個正整數(shù)（n20） ，將它們聯(lián)接成一排，組成一個最大的多位整數(shù)。 例如：n=3 時，3 個整數(shù) 13，312，343 聯(lián)接成的最大整數(shù)為：34331213 又如：n=4 時，4 個整數(shù) 7，13，4，246 聯(lián)接成的最大整數(shù)為：7424613 程序輸入：n n 個數(shù) 程序輸出：聯(lián)接成的多位數(shù) 40% 3著名科學(xué)家盧斯為了檢查學(xué)生對進(jìn)位制的理解，他給出了如下的一張加法表，表中的字 母代表數(shù)字。 例如： 40% 其含義為： L+L=L，L+K=K，L+V=V，L+E=E K+L=K，K+K=V，K+V=E，K+E=KL E+E=KV 根據(jù)這些規(guī)則可推導(dǎo)出：L=0，K=1，V=2，E=3 同時可以確

56、定該表表示的是 4 進(jìn)制加法 程序輸入： n（n9）表示行數(shù)。 以下 n 行，每行包括 n 個字符串，每個字串間用空格隔開。 （字串僅有一個為+號， 其它都由大寫字母組成） 程序輸出： +LKVE LLKVE KKVEKL VVEKLKK EEKLKK KV 各個字母表示什么數(shù)，格式如：L=0，K=1， 加法運(yùn)算是幾進(jìn)制的。 若不可能組成加法表，則應(yīng)輸出“ERROR！” 第四屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽第四屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽 復(fù)賽參考答案（高中組）復(fù)賽參考答案（高中組） 題號輸入輸出分值 1.15 7 32 4135 分 1.20 10 40 685

57、分 1.310 15 2378 813810 分 2.13 121 21 3 3 2 1 1 2 1 5 分 2.24 13 24 75 42 7 5 4 2 2 4 1 310 分 2.34 1341 133 1321 37 3 7 1 3 4 1 1 3 3 1 3 2 110 分 2.46 321 32 407 135 13 217 4 0 7 3 2 3 2 1 2 1 7 1 3 5 1 3 15 分 3.1N=3 + M L M ML M L M L M=1 L=0 二進(jìn)制 5 分 3.2N=4 + M N P M N MP M N MP MM N P M N P M=1 l=2

58、P=0 三進(jìn)制 10 分 3.3N=6 + M L K N H M L H M MK N L H N L MM MK K M L K N H N MK MM N MH ML H N MK H ML MM M=1 l=2 k=0 n=4 h=3 五進(jìn)制 10 分 3.4N=8 + M N L P Q R S M S LL P R M LQ N N LL LR LQ LM N LS LP L P LQ M S L N R P R LM S N P LL LQ Q M N L P Q R S R LQ LS N LL R LP LM S N LP R LQ S LM LL M=2 N=6 L=1 P

59、=3 Q=0 R=5 S=4 七進(jìn)制 15 分 第五屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第五屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （普及組（普及組 競賽用時：競賽用時：3 小時）小時） 第一題第一題 Cantor 表表（30 分） 現(xiàn)代數(shù)學(xué)的著名證明之一是 George Cantor 證明了有理數(shù)是可枚舉的。他是用下面這一 張表來證明這一命題的： 我們以 Z 字形給上表的每一項編號。第 一項是 1/1，然后是 1/2，2/1，3/1，2/2， 輸入：整數(shù) N（1N10000000） 輸出：表中的第 N 項 樣例： INPUT OUTPUT N=7 1/4 第二題

60、第二題 回文數(shù)回文數(shù)（30 分） 若一個數(shù)（首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱之為回文數(shù)。 例如：給定一個 10 進(jìn)制數(shù) 56，將 56 加 56（即把 56 從右向左讀） ，得到 121 是一個回文數(shù)。 又如：對于 10 進(jìn)制數(shù) 87： STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627 = 1353 STEP4：1353+3531 = 4884 在這里的一步是指進(jìn)行了一次 N 進(jìn)制的加法，上例最少用了 4 步得到回文數(shù) 4884。 寫一個程序，給定一個 N（2=N=10，N=16）進(jìn)制數(shù) M，求最少經(jīng)過幾步可以得到 回