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

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

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

4、放的元素為 0N-1 之間的整數，且 AiAj（當 ij 時） 。 例如：N=6 時，有： A=（4，3，0，5，1，2） 此時，數組 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的值小的個數（i=1，2N-

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

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

7、%+6%+8%） 輸入 N=1 （4%） 輸入 N=3 （6%） 結果： 結果： 17 8 1 6 9 2 5 4 3 輸入 N=10（8%） 結果： 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 分 輸出結果為： A 類=538 B 類=462 本題 30 分（15%+15%） 由數組求編碼：共 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） 由編碼求原數組：共 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%） 數據輸入： N=6 P1=R N1=1 Q 數據輸入：N=6 P1=R N1=2 P2=Y N2=1 Q R R R R R R 排列方案： 排列總數=6 RRY RRY RRY RRY RRY RRY 排列方案： 排列總數=12

10、 數據輸入：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 排列方案： 排列總數：

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

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

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

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

15、部由 B 產生） NOI95 “同創杯同創杯”全國青少年信息學（計算機）奧林匹克競賽全國青少年信息學（計算機）奧林匹克競賽 分區聯賽復賽測試數據（高中組）分區聯賽復賽測試數據（高中組） 本題 30 分（15%+15%） 由數組求編碼：共 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） 由編碼求原數組：共 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%） 數據輸入： N=6 P1=R N1=1 Q 數據輸入：N=6 P1=R N1=2 P2=Y N2=1 Q R R R R R R 排列方案： 排列總數=6 RRY RRY RRY RRY RRY RRY 排列方案： 排列總數

17、=12 數據輸入：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 應打印出完整的圖形：（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 排列方案： 排列總數： 1052=210 輸入 1 0 1 0 1 0 1 2 1 2 1 2 1 2 1 應打印出完整的圖形（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 應打印出

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 第二屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題第二屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題 （初中組 競賽用時：3 小時） 1編制一個乘法運算的程序（20 分） 從鍵盤讀入 2 個 100 以內的正整數，進行乘法運算并以豎式輸出。 例如，輸入格式：89

20、13 又如，輸入格式：16 8 輸出格式： 89 輸出格式： 16 13 8 267 128 89 1157 2輸入三個自然數 N，i，j （1=i=N，1=j=N） ，輸出在一個 N*N 格的棋盤中，與格 子（i，j）同行、同列、同一對角線的所有格子的位置。 （20 分） 如：n=4，i=2，j=3 表示了棋盤中的第二行第三列的格子，如下圖： 第一列第二列第三列第四列 (2,3) 當 n=4，i=2，j=3 時，輸出的結果是： (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 個字符） ，并以字符 . 結束。 例如：This is a book. 現對該字符串進行編輯，編輯功能有： D：刪除一個字符，命令的方式為： D a 其中 a 為被刪除的字符 例如：D s 表示刪除字符 s ，若字符串中有多個 s，則刪除第一次出現的。 如上例中刪除的結果為： 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 則應 全部替換。 例如： 原 串： This is a book. 輸入命令：R o e 替換后的字符串為： This is a beek. 在編輯過程中，若出現被改的字符不存在時，則給出提示信息。 4比賽安排（30 分） 設有有

23、2 n（n=6）個球隊進行單循環比賽，計劃在 2 n 1 天內完成，每個隊每天進行 一場比賽。設計一個比賽的安排，使在 2 n 1 天內每個隊都與不同的對手比賽。 例如 n=2 時的比賽安排： 隊 1 23 4 比賽 1=23=4 一天 1=32=4 二天 1=4 2=3 三天 第二屆全國青少年信息學（計算機）奧林匹克分區聯賽第二屆全國青少年信息學（計算機）奧林匹克分區聯賽 復賽參考答案（初中組）復賽參考答案（初中組） 題號輸入輸出 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 第二屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題第二屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題 （高中組（高中組 競賽用時：競賽用時：3 小時）小時） 1比賽安排（20 分） 設有有 2 n（n=6）個球隊進行單循環比賽，計劃在 2 n 1 天內完成，每個隊每天進行 一場比賽。設計一個比賽的安排，使在 2 n 1 天內每個隊都與不同的對手比賽。 例如 n=2 時的比賽安排： 隊 1 23 4 比賽 1=23=4 一天 1=32=4 二天 1=4 2=3 三天 2數制轉換（20 分） 設有一個字符串 A$的結構為： A$=mp 其中 m 為數字串（長度=20）

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

31、地雷的方案， 使某人能挖到最多的地雷。 輸入格式： N： （表示地窖的個數） 1，W2，W3，WN （表示每個地窖中埋藏的地雷數量） 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 （挖地雷的數量） 例如： - - 其輸入格式為： 輸出： 51 3 -4 -5 10，8，4，7，6max=27 1 1 1 0 0 0 0 1 1 1 4砝碼稱重（30 分） 設有 1g、2g、3g、5g、10g、20

32、g 的砝碼各若干枚（其總重=1000） ， 要求： 輸入方式：a1 a2 a3 a4 a5 a6 （表示 1g 砝碼有 a1 個，2g 砝碼有 a2 個，20g 砝碼有 a6 個） 輸出方式：Total=N （N 表示用這些砝碼能稱出的不同重量的個數，但不包括一個砝碼也不 用的情況） 如輸入：1_1_0_0_0_0 （注：下劃線表示空格） 輸出：TOTAL=3 表示可以稱出 1g，2g，3g 三種不同的重量。 第二屆全國青少年信息學（計算機）奧林匹克分區聯賽第二屆全國青少年信息學（計算機）奧林匹克分區聯賽 復賽參考答案（高中組）復賽參考答案（高中組） 題號輸入輸出 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 第三屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題第三屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題 （初中組（初中組 競賽用時：競賽用時：3 小時）小時） 1設有一個 n*m 方格的棋盤（1m,n100） 。 （30%） 求出該棋盤中包含多少個正方形、多少個長方形（不包括正方形） 。 例如：當 n=2，m=3 時 正方形的個數有 8 個；即邊

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

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

41、的路徑僅有兩條。 程序要求： 任務一：給出 N，M 后，求出所有從 A 出發到達 B 的路徑的條數。 任務二：給出 N，M，同時再給出此街道中的矩形障礙區域的 2 對頂點坐標(X1,y1), （X2，Y2） ，然后求出此種情況下所有從 A 出發到達 B 的路徑的條數。 南 * * 東 北 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 ） 第三屆全國青少年信息學（計算機

42、）奧林匹克分區聯賽第三屆全國青少年信息學（計算機）奧林匹克分區聯賽 復賽參考答案（初中組）復賽參考答案（初中組） 題一輸入輸出 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滿足條件的方案數：2（如下） 7 7 3 1 2 3 5 6 6 4 8 2 4 9 8 1 5 9 22P=18無解 23P=19滿足條件的方案數：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滿足條件的方案數：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 題三任 務 一 31N=2，M=22 32N=10，M=1048620 33N=50，M=5058，980，856，902，730，428，6 00 任 務 二 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 第三屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題第三屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題 （高中組（高中組 競賽用時：競賽用時：3 小時）小時） 1在 N*N 的棋盤上（1N10） ，填入 1，2，N*N 共 N*N 個數，使得任意兩個相 鄰的數之和為素數。 （30%） 例如：當 N=2 時，有： 12 43 當 N=4 時，一種可以填寫的方案如下： 121112 161585 134914 67103 在這里我們約定：左上角的格子里必

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

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

47、置和終點的位置，試找出從起點到 終點的所有路徑的數目。 例如：（n=10,m=10） ， （1，5） （起點） ， （3，5） （終點） 輸 出：2（即由（1，5）到（3，5）共有 2 條路徑） 輸入格式：n,m,x1,y1,x2,y2 (分別表示 n,m,起點坐標，終點坐標) 輸出格式：路徑數目（若不存在從起點到終點的路徑，輸出 0） 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 第三屆全國青少年信息學（計算機）奧林匹克分區聯賽第三屆全國青少年信息學（計算機）奧林匹克分區聯賽 復賽測試數據（高中組）復賽測試數據（高中組） 題號輸入輸出 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 題號任 務 一 31N=9，M=5（1，1）-（3，2）-（5，1） （6，3） -（7，1）-（8，3）-（9，5） （答案不唯一） 32N=3，M=3NO 任 務 二 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） 第四屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題第四屆全國青少年信息學（計算機）奧

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

51、此可知，137 可表示為： 2（7）+2（3）+2（0） 進一步：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） 輸入：正整數（n20000） 輸出：符合約定的 n 的 0，2 表示（在表示中不能有空格） 第四屆全國青少年信息學（計算機）奧林匹克分區聯賽第四屆全國青少年信息學（計算機）奧林匹克分區聯賽 復賽

52、參考答案（初中組）復賽參考答案（初中組） 題號輸入輸出分值 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 分 第四屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題第四屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題 （高中組（高中組 競賽用時：競賽用時：3 小時）小時） 1火車從始發

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

55、個正整數（n20） ，將它們聯接成一排，組成一個最大的多位整數。 例如：n=3 時，3 個整數 13，312，343 聯接成的最大整數為：34331213 又如：n=4 時，4 個整數 7，13，4，246 聯接成的最大整數為：7424613 程序輸入：n n 個數 程序輸出：聯接成的多位數 40% 3著名科學家盧斯為了檢查學生對進位制的理解，他給出了如下的一張加法表，表中的字 母代表數字。 例如： 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 根據這些規則可推導出：L=0，K=1，V=2，E=3 同時可以確

56、定該表表示的是 4 進制加法 程序輸入： n（n9）表示行數。 以下 n 行，每行包括 n 個字符串，每個字串間用空格隔開。 （字串僅有一個為+號， 其它都由大寫字母組成） 程序輸出： +LKVE LLKVE KKVEKL VVEKLKK EEKLKK KV 各個字母表示什么數，格式如：L=0，K=1， 加法運算是幾進制的。 若不可能組成加法表，則應輸出“ERROR！” 第四屆全國青少年信息學（計算機）奧林匹克分區聯賽第四屆全國青少年信息學（計算機）奧林匹克分區聯賽 復賽參考答案（高中組）復賽參考答案（高中組） 題號輸入輸出分值 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 二進制 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 三進制 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 五進制 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 七進制 15 分 第五屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題第五屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽試題 （普及組（普及組 競賽用時：競賽用時：3 小時）小時） 第一題第一題 Cantor 表表（30 分） 現代數學的著名證明之一是 George Cantor 證明了有理數是可枚舉的。他是用下面這一 張表來證明這一命題的： 我們以 Z 字形給上表的每一項編號。第 一項是 1/1，然后是 1/2，2/1，3/1，2/2， 輸入：整數 N（1N10000000） 輸出：表中的第 N 項 樣例： INPUT OUTPUT N=7 1/4 第二題

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