提示：文档已分节，可用 word 跳转节功能 本文为本人将 1995-2008 年历届 NOIP 试题、研究成果整理而成，由于“年代久远”所以 有不少资料没有找到。但本人都尽量整理最有价值的信息记录于此。 资料来源皆为网络，若引用请注明出处 一不注意就 208 页了呢 其实最初只是想方便自己，看着一下午的成果，就忍不住放到了 网络上。由于赶时间，质量不太好，而且历届 NOIP 的排版也不一样，只是做了粗略的整 理、排版，若有错误之处，敬请谅解。 回首历届 NOIP，甚至比我自己出生的还早的老题，一代代 OIer 就从这条路上走过，作为 一个不大努力的 OIer，我甚至为自己感到愧疚。总之，为了报答一代代出题人、教师、主 办方以及 OIer 们，在努力一把也不迟啊。 By 2014 年 8 月 15 日（农历二一四年七月二十）星期五 东营市胜利一中 梅如歌 OI95 “同创杯同创杯”全国青少年信息学（计算机）奥林匹克竞赛全国青少年信息学（计算机）奥林匹克竞赛 分区联赛复赛试题（初中组）分区联赛复赛试题（初中组） （上机编程，完成时间：（上机编程，完成时间：210 分钟）分钟） 设有下列的算式： 8 0 9 - ) - - 1 求出中的数字，并打印出完整的算式来。 方阵填数方阵填数：在一个 NN 的方阵中，填入 1，2，NN 个数，并要求构成如下的 格式： 例： 若将一个正整数化为二进制数，在此二进制数中，我们将数字 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；数组中存放的元素为 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- 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 RRBBB 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%+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 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 分（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 数据输入：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 排列方案： 排列总数： 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） 上面数组 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 RRBBB 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 是由第四层相邻的两个数据 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 （即全部由 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