历届NOIP试题及详解

1、à提示：文档已分节，可用word跳转节功能ß本文为本人将1995-2008年历届NOIP试题、研究成果整理而成，由于“年代久远”所以有不少资料没有找到。但本人都尽量整理最有价值的信息记录于此。资料来源皆为网络，若引用请注明出处一不注意就208页了呢 其实最初只是想方便自己，看着一下午的成果，就忍不住放到了网络上。由于赶时间，质量不太好，而且历届NOIP的排版也不一样，只是做了粗略的整理、排版，若有错误之处，敬请谅解。回首历届NOIP，甚至比我自己出生的还早的老题，一代代OIer就从这条路上走过，作为一个不大努力的OIer，我甚至为自己感到愧疚。总之，为了报答一代代出题人、教

2、师、主办方以及OIer们，在努力一把也不迟啊。By 2014年8月15日（农历二一四年七月二十）星期五东营市胜利一中梅如歌OI95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛试题（初中组） （上机编程，完成时间：210分钟）<1> 设有下列的算式： 8 0 9 -) - - 1 求出中的数字，并打印出完整的算式来。<2> 方阵填数：在一个NN的方阵中，填入1，2，NN个数，并要求构成如下的格式：N=616 17 18 19 20 115 30 31 32 21 214 29 36 33 22 313 28 35 34 23 412 27 26 25 2

3、4 511 10 9 8 7 6N=513 14 15 16 112 23 24 17 211 22 25 18 310 21 20 19 4 9 8 7 6 5例：<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之中（包括

4、1与1000），全部A、B两类数的个数。<4> 编码问题：设有一个数组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，2N-1） 上面数组A的编码为：B=（0，0，0，3，1，2） 程序要求解决以下问题： 给出数组A后，求出其编码； 给出数组A的编码后，求出A中的原数据。<5> 灯的排列问题：设在一排上有N个格子（N20），若在格子中放置有不

5、同颜色的灯，每种灯的个数记为N1，N2，Nk（k表示不同颜色灯的个数）。 放灯时要遵守下列规则： 同一种颜色的灯不能分开； 不同颜色的灯之间至少要有一个空位置。 例如：N=8（格子数） R=2（红灯数） B=3（蓝灯数） 放置的方法有： R-B顺序RRBBBRRBBBRRBBBRRBBBRRBBBRRBBB B-R顺序BBBRRBBBRRBBBRRBBBRRBBBRRBBBRR 放置的总数为12种。 数据输入的方式为：NP1（颜色，为一个字母） N1（灯的数量）P2 N2 Q（结束标记，Q本身不是灯的颜色） 程序要求：求出一种顺序的排列方案及排列总数。NOI95 “同创杯”全国青少年信息学（计

6、算机）奥林匹克竞赛分区联赛复赛测试数据（初中组） <1> 正确算式如下：8分12） 809 打印格式占4% 9709 算式不对不给分 96 109 108 1<2> 本题18分（4%+6%+8%） 输入N=1 （4%） 输入N=3 （6%） 结果： 结果：1 7 8 16 9 25 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

7、 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 70 43 8 20 51 50 49 48 47 46 45 44 919 18 17 16 15 14 13 12 11 10<3> 本题14分输出结果为： A类=538 B类=462<4> 本题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=（

8、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%+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）<5> 本题共30分（10%+10%+10%） 数据输入： N=6 P1=R

9、 N1=1 QRRRRRR排列方案：排列总数=6 数据输入：N=6 P1=R N1=2 P2=Y N2=1 QRRYRRYRRYRRYRRYRRY排列方案：排列总数=12 数据输入：N=12 P1=R N1= 3 P2=B N2=2 P3=Y N3=1 QRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRB

10、BYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBY排列方案：排列总数：105×2=210 NOI95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛试题（高中组） （上机编程，完成时间：210分钟）<1> 编码问题： 设有一个数组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） 上面数组A的

11、编码为： B=（0，0，0，3，1，2） 程序要求解决以下问题： 给出数组A后，求出其编码。 给出数组A的编码后，求出A中的原数据。<2> 灯的排列问题： 设在一排上有N个格子（N20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，Nk（k表示不同颜色灯的个数）。 放灯时要遵守下列规则： 同一种颜色的灯不能分开； 不同颜色的灯之间至少要有一个空位置。 例如：N=8（格子数） R=2（红灯数） B=3（蓝灯数） 放置的方法有： R-B顺序RRBBBRRBBBRRBBBRRBBBRRBBBRRBBB B-R顺序BBBRRBBBRRBBBRRBBBRRBBBRRBBBRR

12、放置的总数为12种。 数据输入的方式为：NP1（颜色，为一个字母） N1（灯的数量）P2 N2 Q（结束标记，Q本身不是灯的颜色） 程序要求：求出一种顺序的排列方案及排列总数。<3> 设有一个四层的积木块，14层积木块的数量依次为：5，6，7，8 如下图所示放置：815851691423414326 其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。 计算的方法是：第三层的某个数据A是由第四层相邻的两个数据B，C经过某种计算后产生的：ABC 计算所用到的计算符为：+，-，且无优先级之分（自左向右计算），运算符最多为2个。 如：3+45=35 54+

13、3=23 可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的：A=BC+B 也就是：8=23+2，15=34+3，14=26+2 程序要求： 给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。 输入数据不存在出错的情况，同时也不会超过整数的范围。 计算时可允许出现以下情况： A=B （即可理解为运算符的个数为零） A=BB+B （即全部由B产生）NOI95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛测试数据（高中组） <6> 本题30分（15%+15%） 由数组求编码：共15分（5%+5%+5%

14、）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%+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

15、） 输出编码： A=（3，2，1，0，4，5，6）<7> 本题共30分（10%+10%+10%） 数据输入： N=6 P1=R N1=1 QRRRRRR排列方案：排列总数=6 数据输入：N=6 P1=R N1=2 P2=Y N2=1 QRRYRRYRRYRRYRRYRRY排列方案：排列总数=12 数据输入：N=12 P1=R N1= 3 P2=B N2=2 P3=Y N3=1 QRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYR

16、RRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBY排列方案：排列总数：105×2=210 <8> 本题共40分（12%+14%+14%） 输入3 4 4 4 4 3 41 2 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 输入 1 0 1 0 1 0 1 2 1 2 1 2

17、 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=B×C-C 输入 2 4 2 4 2 4 2 2 1 2 1 2 1 2 1 应打印出完整的图形：（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=B×C×C 或： 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

18、=B+B第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （初中组 竞赛用时：3小时）1编制一个乘法运算的程序（20分） 从键盘读入2个100以内的正整数，进行乘法运算并以竖式输出。 例如，输入格式：8913 又如，输入格式：16 8 输出格式： 89 输出格式： 16 × 13 × 8 267 128 89 11572输入三个自然数N，i，j （1<=i<=N，1<=j<=N），输出在一个N*N格的棋盘中，与格子（i，j）同行、同列、同一对角线的所有格子的位置。（20分） 如：n=4，i=2，j=3表示了棋盘中的第二行第三列的格子，如下图：

19、第1行第2行第3行第4行 第一列第二列第三列第四列(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) 左上到右下对角线上的格子的位置 (4,1) (3,2) (2,3) (1,4) 左下到右上对角线上的格子的位置3字符串编辑（30分） 从键盘输入一个字符串（长度<=40个字符），并以字符 . 结束。 例如：This is a book. 现对该字符串进行编辑，编辑功能有： D：删除一个字符，命令的方式为： D a 其

20、中a为被删除的字符 例如：D s 表示删除字符 s ，若字符串中有多个 s，则删除第一次出现的。 如上例中删除的结果为： Thi is a book.I：插入一个字符，命令的格式为： I a1 a2 其中a1表示插入到指定字符前面，a2表示将要插入的字符。例如：I s d 表示在指定字符 s 的前面插入字符 d ，若原串中有多个 s ，则插入在最后一个字符的前面，如上例中： 原 串：This is a book. 插入后：This ids a book.R：替换一个字符，命令格式为： R a1 a2 其中a1为被替换的字符，a2为替换的字符，若在原串中有多个a1则应全部替换。例如： 原 串：

21、This is a book.输入命令：R o e 替换后的字符串为： This is a beek.在编辑过程中，若出现被改的字符不存在时，则给出提示信息。4比赛安排（30分） 设有有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 1012 25 40 25

22、 ×40 00 100 100013 87 76 87 ×76 522 609 661214 3 78 3 ×78 24 21 234题号输入输出21N=4i=4j=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=1i=1j=1（1，1）（1，1）（1，1）（1，1）23N=5i=3j=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

23、）（1，5）24N=6i=4j=6（4，1）（4，2）（4，3）（4，4）（4，5）（4，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 2a13 b12 aa32原串：abc dc e .命令：I c f abc dfc e.33原串：sssssss.命令：I s tssssssts.34原串：abababab.命令：d baababab.35原串：abcd adc命令：r d cabcc acc.36原串：abcd efg.命令：r s t指定字符不

24、存在信息37原串：a命令：r . a aa38原串：ababababab.命令：r b a aaaaaaaaaa.39原串：sssssss ss.命令：r s t ttttttt tt.310原串：.命令：r . %题号输入输出41n=1<1>1-242n=2<1>1-2，3-4<2>1-3，2-4<3>1-4，2-343n=3<1>1-2，3-4，5-6，7-8<2>1-3，2-4，5-7，6-8<3>1-4，2-3，5-8，6-7<4>1-5，2-6，3-7，4-8<5>1-6，2-

25、5，3-8，4-7<6>1-7，2-8，3-5，4-6<7>1-8，2-7，3-6，4-544n=4<1>1-2，3-4，5-6，7-8，9-10， 11-12，13-14，15-16<2>1-3，2-4，5-7，6-8，9-11， 10-12，13-15，14-16<3>1-4，2-3，5-8，6-7，9-12， 10-11，13-16，14-15<4>1-5，2-6，3-7，4-8，9-13， 10-14，11-15，12-16<5>1-6，2-5，3-8，4-7，9-14， 10-13，11-16，12-

26、15<6>1-7，2-8，3-5，4-6，9-15， 10-16，11-13，12-14<7>1-8，2-7，3-6，4-5，9-16， 10-15，11-14，12-13<8>1-9，2-10，3-11，4-12， 5-13， 6-14，7-15，8-16<9>1-10，2-9，3-12，4-11，5-14， 6-13，7-16，8-15<10>1-11，2-12，3-9，4-10，5-15， 6-16，7-13，8-14<11>1-12，2-11，3-10，4-9，5-16， 6-15，7-14，8-13<12&

27、gt;1-13，2-14，3-15，4-16，5-9， 6-10，7-11，8-12<13>1-14，2-13，3-16，4-15，5-10， 6-9，7-12,8-11<14>1-15，2-16，3-13，4-14，5-11， 6-12，7-9，8-10<15>1-16，2-15，3-14，4-13，5-12， 6-11，7-10，8-9第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （高中组 竞赛用时：3小时）1比赛安排（20分） 设有有2 n（n<=6）个球队进行单循环比赛，计划在2 n 1天内完成，每个队每天进行一场比赛。设计一个比赛

28、的安排，使在2 n 1天内每个队都与不同的对手比赛。例如n=2时的比赛安排： 队 1 23 4 比赛 1=23=4 一天 1=32=4 二天 1=4 2=3 三天2数制转换（20分） 设有一个字符串A$的结构为： A$=m<n>p 其中m为数字串（长度<=20），而n,p均为1或2位的数字串（其中所表达的内容在2-10之间）。 程序要求：从键盘上读入A$后（不用正确性检查），将A$中的数字串m(n进制)，以p进制的形式输出。 例如：A$=48<10>8 其意义为：将10进制数48，转换成8进制数输出。 输出结果为：48<10>=60<8>4

29、挖地雷（30分） 在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。V1 V 2 V3 V4 V5 例如：题目要求当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。 输入格式： N： （表示地窖的个数） 1，W2，W3，WN （表示每个地窖中埋藏的地雷数量）地窖之间连接路径（其中ij=1表示地窖i,j之间是否有通路：通Aij=1,不通Aij=0） A12 . A1N A23.A2N . AN-1 N 输出格式：

30、K1-K2-.KV （挖地雷的顺序） MAX （挖地雷的数量）例如： - -其输入格式为： 输出： 51 3 -4 -510，8，4，7，6max=27 1 1 1 0 0 0 0 1 1 14砝码称重（30分）设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），要求： 输入方式：a1 a2 a3 a4 a5 a6 （表示1g砝码有a1个，2g砝码有a2个，20g砝码有a6个） 输出方式：Total=N （N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）如输入：1_1_0_0_0_0 （注：下划线表示空格） 输出：TOTAL=3 表示可以

31、称出1g，2g，3g三种不同的重量。第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛参考答案（高中组）题号输入输出11n=1<1>1-212n=2<1>1-2，3-4<2>1-3，2-4<3>1-4，2-313n=3<1>1-2，3-4，5-6，7-8<2>1-3，2-4，5-7，6-8<3>1-4，2-3，5-8，6-7<4>1-5，2-6，3-7，4-8<5>1-6，2-5，3-8，4-7<6>1-7，2-8，3-5，4-6<7>1-8，2-7，3-6，4

32、-514n=4<1>1-2，3-4，5-6，7-8，9-10， 11-12，13-14，15-16<2>1-3，2-4，5-7，6-8，9-11， 10-12，13-15，14-16<3>1-4，2-3，5-8，6-7，9-12， 10-11，13-16，14-15<4>1-5，2-6，3-7，4-8，9-13， 10-14，11-15，12-16<5>1-6，2-5，3-8，4-7，9-14， 10-13，11-16，12-15<6>1-7，2-8，3-5，4-6，9-15， 10-16，11-13，12-14<7

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

34、4，2-13，3-16，4-15，5-10， 6-9，7-12,8-11<14>1-15，2-16，3-13，4-14，5-11， 6-12，7-9，8-10<15>1-16，2-15，3-14，4-13，5-12， 6-11，7-10，8-9题号输入输出21101<2>10101<2>=5<10>221101<10>21101<10>=<2>233704<8>103704<8>=1988<10>2473<10>873<10>=111<

35、;8>2544<7>844<7>=40<8>2662<8>562<8>=200<5>27934<10>7934<10>=2503<7>28221<9>6221<9>=501<6>29443<5>7443<5>=234<7>21061<8>361<8>=1211<3>题号输入输出31n=3w1=10,w2=20,w3=50 1 02MAX=2032n=3w1=5,w2=10,w

36、3=51 1 01-2-3MAX=2033n=6w1=5,w2=10,w3=20w4=5,w5=4,w6=51 0 1 0 0 0 1 0 0 1 0 0 1 1 13-4-2-1MAX=4034n=6w1=10,w2=15,w3=20w4=15,w5=5, w6=100 0 0 0 0 0 0 0 0 0 0 0 0 0 03MAX=2035n=11w1=10,w2=20,w3=30w4=15,w5=40, w6=10w7=20,w8=40, w9=10w10=5,w11=2001 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 111-10-9-7-8-6-2-5-4-3-1MAX=400题号输入输出411 1 0 0 0 0Total=3422 2 0 0 0 0Total=6431 0 3 0 0 0Total=7443 4 0 5 0 0Total=36452 2 2 2 2 2Total=82460 3 2 7 4 5Total=185470 6 3 4 2 1Total=