1995-2008 历届NOIP试题及详解

1995-2008 NOIP复赛试题

?提示：文档已分节，可用word跳转节功能?

本文为本人将1995-2008年历届NOIP试题、研究成果整理而成，由于“年代久远”所以有不少资料没有找到。但本人都尽量整理最有价值的信息记录于此。

资料来源皆为网络，若引用请注明出处

一不注意就208页了呢~ 其实最初只是想方便自己，看着一下午的成果，就忍不住放到了网络上。由于赶时间，质量不太好，而且历届NOIP的排版也不一样，只是做了粗略的整理、排版，若有错误之处，敬请谅解。

回首历届NOIP，甚至比我自己出生的还早的老题，一代代OIer就从这条路上走过，作为一个不大努力的OIer，我甚至为自己感到愧疚。总之，为了报答一代代出题人、教师、主办方以及OIer们，在努力一把也不迟啊。 By

2014年8月15日（农历二〇一四年七月二十）星期五

东营市胜利一中

梅如歌

第1页 | 共209页

NOIP 1995 普及组 复赛测试数据

OI’95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛

分区联赛复赛试题（初中组） （上机编程，完成时间：210分钟）

<1> 设有下列的算式：

8 0 9 ------------- □□) □□□□ □□ ------------- □□□ □□□ ------------- 1

求出□中的数字，并打印出完整的算式来。

<2> 方阵填数：在一个N?N的方阵中，填入1，2，??N?N个数，并要求构成如下的格式：

例：

N=6 N=5

16 17 18 19 20 1 13 14 15 16 1

15 30 31 32 21 2 12 23 24 17 2

14 29 36 33 22 3 11 22 25 18 3

13 28 35 34 23 4 10 21 20 19 4

12 27 26 25 24 5 9 8 7 6 5

11 10 9 8 7 6

<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类数； 程序要求：求出1～1000之中（包括1与1000），全部A、B两类数的个数。

<4> 编码问题：设有一个数组A:ARRAY[0..N-1] OF INTEGER；数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i≠j时）。

例如：N=6时，有： A=（4，3，0，5，1，2） 此时，数组A的编码定义如下： A[0]的编码为0；

第2页 | 共209页

NOIP 1995 普及组 复赛测试数据

A[i]的编码为：在A[0]，A[1]，??A[i-1]中比A[i]的值小的个数（i=1，2??N-1） ∴上面数组A的编码为： B=（0，0，0，3，1，2） 程序要求解决以下问题：

① 给出数组A后，求出其编码；

② 给出数组A的编码后，求出A中的原数据。

<5> 灯的排列问题：设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，??Nk（k表示不同颜色灯的个数）。 放灯时要遵守下列规则：

①同一种颜色的灯不能分开；

②不同颜色的灯之间至少要有一个空位置。 例如：N=8（格子数） R=2（红灯数） B=3（蓝灯数） 放置的方法有： R-B顺序

R R R

B-R顺序

B B B B B B B B B B B B B B B B B R B R R R R R R R R R R R R R R R R R R R B R B B B B B B B B B B B B B B B B B 放置的总数为12种。 数据输入的方式为：

N

P1（颜色，为一个字母） N1（灯的数量） P2 N2 ??

Q（结束标记，Q本身不是灯的颜色）

程序要求：求出一种顺序的排列方案及排列总数。

第3页 | 共209页

NOIP 1995 普及组 复赛测试数据

NOI’95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛

分区联赛复赛测试数据（初中组）

<1> 正确算式如下：8分

809 ① 打印格式占4% 12）

9709 ② 算式不对不给分 96 109 108 1

<2> 本题18分（4%+6%+8%）

① 输入N=1 （4%） ② 输入N=3 （6%） 结果：

1

结果：

7 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

19 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）

第4页 | 共209页