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页

NOIP 1995 普及组 复赛测试数据

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）

<5> 本题共30分（10%+10%+10%）

① 数据输入： N=6

P1=R N1=1 Q 排列方案： R

排列总数=6

② 数据输入：N=6

P1=R N1=2 P2=Y N2=1 Q 排列方案： R 排列总数=12 R R

R R R R R R R Y Y Y Y Y R R R R 第5页 | 共209页

NOIP 1996 普及组 复赛试题

R B B

R R R B B Y

R R R B B Y

R R R B B R R R B B Y R R R B B R R R B B

R R R B B Y

R R R B B Y

R R R B B

<8> 本题共40分（12%+14%+14%） ① 输入 3 4 4 4 4 3 4 1 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

第11页 | 共209页

⑥ 数据输入：N=12

P1=R N1= 3 P2=B N2=2 P3=Y N3=1 Q 排列方案： R R R 排列总数：

R R R 105×2=210 R R R

R R R

R R R

R R R

R R R

R R R R R R R R R R R R R R R

R R R

R R R

R R R

R R

R R

R R

R R R R R B B B B B B B B B B B B B B B B B B B B B B B B B B B Y B B B B B Y Y B B B Y Y Y Y B Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y NOIP 1996 普及组 复赛试题

② 输入 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=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=B+B

第12页 | 共209页

NOIP 1996 普及组 复赛试题

第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题

（初中组 竞赛用时：3小时）

1．编制一个乘法运算的程序（20分）

从键盘读入2个100以内的正整数，进行乘法运算并以竖式输出。

例如，输入格式：8913 又如，输入格式：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表示了棋盘中的第二行第三列的格子，如下图： 第一列 第二列 第三列 第四列 第1行 (2,3) 第2行 第3行 第4行

当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 其中a为被删除的字符

例如：D s 表示删除字符 ’s’ ，若字符串中有多个 ‘s’，则删除第一次出现的。 如上例中删除的结果为： ‘Thi is a book.’ I：插入一个字符，命令的格式为：

I a1 a2 其中a1表示插入到指定字符前面，a2表示将要插入的字符。

例如：I s d 表示在指定字符 ’s’ 的前面插入字符 ‘d’ ，若原串中有多个 ‘s’ ，则插入在最后一个字符的前面，如上例中：

第13页 | 共209页

NOIP 1996 普及组 复赛试题

原 串：’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分）

设有有2 n（n<=6）个球队进行单循环比赛，计划在2 n – 1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2 n – 1天内每个队都与不同的对手比赛。

例如n=2时的比赛安排： 队 1 2 3 4 比赛 1==2 3==4 一天 1==3 2==4 二天 1==4 2==3 三天

第14页 | 共209页

NOIP 1996 普及组 测试数据

第二届全国青少年信息学（计算机）奥林匹克分区联赛

复赛参考答案（初中组）

题号 1．1 输入 5 2 25 40 5 ×2 10 25 ×40 00 100 1000 87 ×76 522 609 6612 3 ×78 24 21 234 输出 （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） （1，1） （1，1） （1，1） （1，1） （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） （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．2 1．3 87 76 1．4 3 78 题号 2．1 输入 N=4 i=4 j=1 N=1 i=1 j=1 N=5 i=3 j=3 N=6 i=4 2．2 2．3 2．4 第15页 | 共209页

NOIP 1996 普及组 测试数据

j=6 题号 3．1 3．2 3．3 3．4 3．5 3．6 3．7 3．8 3．9 （1，3）（2，4）（3，5）（4，6） （6，4）（5，5）（4，6） 输入 输出 a13 b12 aa abc dfc e. ssssssts. aababab. abcc acc. 指定字符不存在信息 aa aaaaaaaaaa. ttttttt tt. % 原串：a123 b12 aa. 命令：d 2 原串：abc dc e . 命令：I c f 原串：sssssss. 命令：I s t 原串：abababab. 命令：d b 原串：abcd adc 命令：r d c 原串：abcd efg. 命令：r s t 原串：a． 命令：r . a 原串：ababababab. 命令：r b a 原串：sssssss ss. 命令：r s t 3．10 原串：. 命令：r . ％ 题号 4．1 4．2 n=1 n=2 输入 输出 <1>1-2 <1>1-2，3-4 <2>1-3，2-4 <3>1-4，2-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-5 <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 4．3 n=3 4．4 n=4 第16页 | 共209页

NOIP 1996 普及组 测试数据

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

第17页 | 共209页

NOIP 1996 提高组 复赛试题

第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题

（高中组 竞赛用时：3小时）

1．比赛安排（20分）

设有有2 n（n<=6）个球队进行单循环比赛，计划在2 n – 1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2 n – 1天内每个队都与不同的对手比赛。 例如n=2时的比赛安排： 队 1 2 3 4 比赛 1==2 3==4 一天 1==3 2==4 二天 1==4 2==3 三天 2．数制转换（20分）

设有一个字符串A$的结构为： A$=’mp’ 其中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．挖地雷（30分）

在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。

例如：

V1 V 2 V3 V4 V5 [题目要求]

当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入格式： N： （表示地窖的个数）

Ｗ1，W2，W3，……WN （表示每个地窖中埋藏的地雷数量） A12…………… . A1N 地窖之间连接路径（其中Ａij=1表示地窖i,j

A23…………..A2N 之间是否有通路：通Aij=1,不通Aij==0）

……..

AN-1 N

输出格式：

第18页 | 共209页

NOIP 1996 提高组 复赛试题

K1--K2--……….KV （挖地雷的顺序） MAX （挖地雷的数量）

例如：

⑩--------⑧ ④-----⑦-------⑥

其输入格式为： 输出： 5 1 –3 -4 -5

10，8，4，7，6 max=27 1 1 1 0 0 0 0 1 1 1

4．砝码称重（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 表示可以称出1g，2g，3g三种不同的重量。

第19页 | 共209页

NOIP 1996 提高组 测试数据

第二届全国青少年信息学（计算机）奥林匹克分区联赛

复赛参考答案（高中组）

题号 1．1 n=1 1．2 n=2 输入 <1>1-2 <1>1-2，3-4 <2>1-3，2-4 <3>1-4，2-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-5 <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>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-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 第20页 | 共209页

输出 1．3 n=3 1．4 n=4

NOIP 1996 提高组 测试数据

<15>1-16，2-15，3-14，4-13，5-12， 6-11，7-10，8-9 题号 2．1 2．2 2．3 2．4 2．5 2．6 2．7 2．8 2．9 题号 3．1 输入 n=3 w1=10,w2=20,w3=5 0 1 0 n=3 w1=5,w2=10,w3=5 1 1 0 n=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 n=6 w1=10,w2=15,w3=20 w4=15,w5=5, w6=10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 n=11 w1=10,w2=20,w3=30 w4=15,w5=40, w6=10 w7=20,w8=40, w9=10 2 MAX=20 输出 输入 101<2>10 1101<10>2 3704<8>10 73<10>8 44<7>8 62<8>5 934<10>7 221<9>6 443<5>7 输出 101<2>=5<10> 1101<10>=10001001101<2> 3704<8>=1988<10> 73<10>=111<8> 44<7>=40<8> 62<8>=200<5> 934<10>=2503<7> 221<9>=501<6> 443<5>=234<7> 61<8>=1211<3> 2．10 61<8>3 3．2 1-2-3 MAX=20 3．3 3-4-2-1 MAX=40 3．4 3 MAX=20 3．5 11-10-9-7-8-6-2-5-4-3-1 MAX=400 第21页 | 共209页

NOIP 1996 提高组 测试数据

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 题号 4．1 4．2 4．3 4．4 4．5 4．6 4．7 4．8 4．8

输入 1 1 0 0 0 0 2 2 0 0 0 0 1 0 3 0 0 0 3 4 0 5 0 0 2 2 2 2 2 2 0 3 2 7 4 5 0 6 3 4 2 1 1 2 3 4 5 6 6 5 4 3 2 1 Total=3 Total=6 Total=7 Total=36 Total=82 Total=185 Total=79 Total=204 Total=83 Total=140 输出 4．10 10 10 10 10 1 1 第22页 | 共209页

NOIP 1997 普及组 复赛试题

第三届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题

（初中组 竞赛用时：3小时）

1．设有一个n*m方格的棋盘（1≤m,n≤100）。（30%）

求出该棋盘中包含多少个正方形、多少个长方形（不包括正方形）。

例如：当n=2，m=3时

正方形的个数有8个；即边长为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

其中：a～i分别表示1，2，······,9中的一个数字，并要求同时满足下列条件： （1）a

（2）b

（3）a+b+d+f=f+g+h+i=i+e+c+a=P

程序要求：

根据输入的边长之和P

输出所有满足上述条件的三角形的个数以及其中的一种方案。

第23页 | 共209页

NOIP 1997 普及组 复赛试题

3．设有一个N＊M（l≤ N≤50， l≤ M≤ 50）的街道（如下图）：（40%）

北

B（9，5） 5

4

东 * * * * * * 3 西

2 * * * * * *

1

1 2 3 4 5 6 7 8 9 南 A（1，1）

规定行人从A(1,1)出发，在街道上只能向东或北方向行走。

如下为N＝3，M=3的街道图，从A出发到达B共有6条可供行走的路径：

A6 A7 B（N，M） 1.A-A1-A2-A5-B 2. A-A1-A4-A5-B A3 A4 A5 3. A-A1-A4-A7-B 4. A-A3-A4-A5-B A A1 A2 5. A-A3-A4-A7-B 6. A-A3-A6-A7-B

若在N＊M的街道中，设置一个矩形障碍区域（包括围住该区域的街道）不让行人通行，如图中用“＊”表示的部分。

此矩形障碍区域用2对顶点坐标给出,前图中的2对顶点坐标为:(2，2),(8，4),此时从 A出发到达B的路径仅有两条。

程序要求：

任务一：给出N，M后，求出所有从A出发到达B的路径的条数。

任务二：给出N，M，同时再给出此街道中的矩形障碍区域的2对顶点坐标(X1,y1), （X2，

Y2），然后求出此种情况下所有从A出发到达B的路径的条数。

第24页 | 共209页

NOIP 1997 普及组 测试数据

第三届全国青少年信息学（计算机）奥林匹克分区联赛

复赛参考答案（初中组）

题一 1．1 1．2 1．3 1．4 1．5 题二 2．1 输入 P=23 输出 满足条件的方案数：2（如下） 7 7 3 1 2 3 5 6 6 4 8 2 4 9 8 1 5 9 无解 满足条件的方案数：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 6 8 9 3 1 8 7 3 4 5 7 满足条件的方案数：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 第25页 | 共209页

输入 N=1，M=1 N=2，M=2 N=10，M=10 N=20，M=20 N=50，M=50 1，0 5，4 385，2640 输出 4970，92680 42925，1582700 2．2 2．3 P=18 P=19 2．4 P=20

NOIP 1997 普及组 测试数据

8 9 9 7 5 2 7 6 5 1 8 6 题三 3．1 3．2 3．3 3．4 3．5 3．6

N=2，M=2 N=10，M=10 N=50，M=50 N=30，M=40 （5，5），（15，15） N=50，M=50 （2，2），（49，49） N=50，M=50 （2，2），（7，5） 任 务 一 2 48620 58，980，856，902，730，428，600 118，200．946，737，728，400 2 36，014，973，809，750，037，800 任 务 二 第26页 | 共209页

NOIP 1997 提高组 复赛试题

第三届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题

（高中组 竞赛用时：3小时）

1．在N*N的棋盘上（1≤N≤10），填入1，2，?，N*N共N*N个数，使得任意两个相邻的数之和为素数。（30%） 例如：当N=2时，有：

其相邻数的和为素数的有： 1 2 1+2，1+4，4+3，2+3 4 3 当N=4时，一种可以填写的方案如下： 1 16 13 6 2 15 4 7 11 8 9 10 12 5 14 3 在这里我们约定：左上角的格子里必须填数字1。 程序要求： 输入：N；

输出：如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输

出“NO！”。

2．代数表达式的定义如下：

a 字母

b c

例如，下面的式子是合法的代数表达式：

a；

第27页 | 共209页

NOIP 1997 提高组 复赛试题

a+b*(a+c); a*a/(b+c)

下面的式子是不合法的代数表达式：

ab;

a+a*/(b+c);

程序要求：

输入：输入一个字符串，以“；”结束，“；”本身不是代数表达式中字符，仅作为

结束）；

输出：若表达式正确，则输出“OK”；若表达式不正确，则输出“ERROR”，及错

误类型。

错误类型约定：

1．式了中出现不允许的字符； 2．括号不配对； 3．其它错误。

例如：输入：a+(b); 输出：OK

例如：输入：a+(b+c*a; 输出：ERROR 2

3．骑士游历：

设有一个n*m的棋盘（2≤n≤50，2≤m≤50），如下图，在棋盘上左下角有一个中国象棋马。

（n,m）

马 (1,1) 马走的规则为： （1） 马走日字； （2） 马只能向右走 即如下图如示：

任务1：当n,m输入之后，找出一条从左下角到右上角的路径。 例如，输入：n=4，m=4 (4,4) (1,1)

第28页 | 共209页

NOIP 1997 提高组 复赛试题

输出：路径的格式：(1,1)→(2,3)→(4,4)。若不存在路径，则输出‘NO’ 任务2：当n，m给出之后，同时给出马起点的位置和终点的位置，试找出从起点到终

点的所有路径的数目。

例如：（n=10,m=10），（1，5）（起点），（3，5）（终点）

10

9

8 7 6

5

4 3 2

1

1 2 3 4 5 6 7 8 9 10

输 出：2（即由（1，5）到（3，5）共有2条路径）

输入格式：n,m,x1,y1,x2,y2 (分别表示n,m,起点坐标，终点坐标) 输出格式：路径数目（若不存在从起点到终点的路径，输出0）

第29页 | 共209页

NOIP 1997 提高组 测试数据

第三届全国青少年信息学（计算机）奥林匹克分区联赛

复赛测试数据（高中组）

题号 1．1 1．2 1．3 1．4 输入 N=1 N=2 N=3 N=4 NO 1 2 4 3 NO 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 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 输出 Error 1 Ok Error 3 Error 2 Error 2 输出 1．5 N=5 题号 2．1 2．2 2．3 2．4 2．5 题号 3．1 任 务 一 N=9，M=5 （1，1）-（3，2）-（5，1）（6，3） -（7，1）-（8，3）-（9，5） （答案不唯一） NO a+x (((b+c))) a+b(c+a) (a+(b+c) a+)b+c( 输入 3．2 3．3 3．4 3．5 3．6 N=3，M=3 任 务 二 2 N=30，M=30 （1，15），（3，15） 8 N=30，M=30 （1，15），（5，15） 460 N=30，M=30 （1，15），（10，15） N=50，M=50 3，323，759，302，857，476 （1，25），（40，25） 第30页 | 共209页

NOIP 1998 普及组 复赛试题

第四届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题

（初中组上机编程 竞赛用时：3小时）

1．将1，2，?，9共9个数分成三组，分别组成三个三位数，且使这三个三位数构成 1：2：3的比例，试求出所有满足条件的三个三位数。

例如：三个三位数192，384，576满足以上条件。 {30%}

2．用高精度计算出S=1！+2！+3！+?+n！（n≤50） 其中“！”表示阶乘，例如：5！=5*4*3*2*1。

输入正整数N，输出计算结果S。 {30%}

3．任何一个正整数都可以用2的幂次方表示。例如： {40%} 137=27+23+20

同时约定方次用括号来表示，即ab 可表示为a（b）。 由此可知，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） 输入：正整数（n≤20000）

输出：符合约定的n的0，2表示（在表示中不能有空格）

第31页 | 共209页

NOIP 1998 普及组 测试数据

第四届全国青少年信息学（计算机）奥林匹克分区联赛

复赛参考答案（初中组）

题号 1.1 输入 无 192 384 576 219 438 657 273 546 819 327 654 981(共四组) 2.1 2.2 2.3 2.4 3.1 3.2 3.3 3.4 3.5 N=6 N=10 N=22 N=48 73 136 255 1384 16385 873 4,037,913 1,177,652 ,997,443 ,428,940 313 12,678,163,798,554,051,767,172,643,373,255, 731,925,167,694,226,950,680,420,940,313 2(2(2)+2)+2(2+2(0))+2(0) 2(2(2)+2+2(0))+2(2+2(0)) 2(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) 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2)+2(2(2)+2(0))+2(2+2(0)) 2(2(2+2(0))+2(2)+2)+2(0) 10分 10分 5分 5分 10分 5分 5分 10分 10分 输出 分值 30分

第32页 | 共209页

NOIP 1998 提高组 复赛试题

第四届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题

（高中组 竞赛用时：3小时）

1．火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。从第3站起（包括第3站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有N个车站，始发站上车的人数为a，最后一站下车的人数是m（全部下车）。试问x站开出时车上的人数是多少？ 输入：a，n，m和x

输出：从x站开出时车上的人数。 {20%}

2．设有n个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。 例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213 又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613 程序输入：n

n个数

程序输出：联接成的多位数 {40%}

3．著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。 例如： {40%}

+ L K V E L L K V E K V K V E E

其含义为：

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

V E KL E KL KK KL KK KV ??

根据这些规则可推导出：L=0，K=1，V=2，E=3

同时可以确定该表表示的是4进制加法

程序输入：

n（n≤9）表示行数。

以下n行，每行包括n个字符串，每个字串间用空格隔开。（字串仅有一个为‘+’号，其它都由大写字母组成）

程序输出：

① 各个字母表示什么数，格式如：L=0，K=1，??

第33页 | 共209页

NOIP 1998 提高组 复赛试题

② 加法运算是几进制的。

③ 若不可能组成加法表，则应输出“ERROR！”

第34页 | 共209页

NOIP 1998 提高组 测试数据

第四届全国青少年信息学（计算机）奥林匹克分区联赛

复赛参考答案（高中组）

题号 1.1 1.2 1.3 2.1 2.2 2.3 2.4 3.1 输入 5 7 32 4 0 10 40 6 10 15 2378 8 3 121 21 3 4 13 24 75 42 4 1341 133 1321 37 6 321 32 407 135 13 217 N=3 + M L M ML M L M L N=4 + M N P M N MP M N MP MM N P M N P N=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 N=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 13 8 138 3 2 1 1 2 1 7 5 4 2 2 4 1 3 3 7 1 3 4 1 1 3 3 1 3 2 1 4 0 7 3 2 3 2 1 2 1 7 1 3 5 1 3 M=1 L=0 二进制 M=1 l=2 P=0 三进制 输出 分值 5分 5分 10分 5分 10分 10分 15分 5分 3.2 10分 3.3 M=1 l=2 k=0 n=4 h=3 五进制 10分 3.4 M=2 N=6 L=1 P=3 Q=0 R=5 S=4 七进制 15分

第35页 | 共209页

NOIP 2000 普及组 复赛试题

普及组复赛 试题（三小时完成 ）

2000年12月2日（农历二〇〇〇年十一月初七）

普及组 题一 计算器的改良 (18分) 问题描述 NCL是一家专门从事计算器改良与升级的实验室，最近该实验室收到了某公司所委托的一个任务：需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交给了一个刚进入的新手ZL先生。为了很好的完成这个任务，ZL先生首先研究了一些一元一次方程的实例：

4＋3x＝8

6a－5＋1＝2－2a －5＋12y＝0

ZL先生被主管告之，在计算器上键入的一个一元一次方程中，只包含整数、小写字母及＋、－、＝这三个数学符号（当然，符号“─”既可作减号，也可作负号）。方程中并没有括号，也没有除号，方程中的字母表示未知数。

问题求解

编写程序，解输入的一元一次方程, 将解方程的结果(精确至小数点后三位)输出至屏幕。

你可假设对键入的方程的正确性的判断是由另一个程序员在做，或者说可认为键入的一元一次方程均为合法的，且有唯一实数解。 样 例

输入：

6a－5＋1＝2－2a

输出：

a＝0.750

第41页 | 共209页

NOIP 2000 普及组 复赛试题

普及组 题二．税收与补贴问题 （20分） 问题描述 每样商品的价格越低，其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量（产品不会低于成本销售），并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后，销量以某固定数值递减。（我们假设价格及销售量都是整数）

对于某些特殊商品，不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。（所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币）

问题求解 你是某家咨询公司的项目经理，现在你已经知道政府对某种商品的预期价格，以及在各种价位上的销售情况。要求你确定政府对此商品是应收税还是补贴的最少金额（也为整数），才能使商家在这样一种政府预期的价格上，获取相对其他价位上的最大总利润。 总利润 = 单位商品利润 * 销量 单位商品利润 = 单位商品价格 – 单位商品成本 （– 税金 or + 补贴）

输 入 输入的第一行为政府对某种商品的预期价，第二行有两个整数，第一个整数为商品成本，第二个整数为以成本价销售时的销量售，以下若干行每行都有两个整数，第一个为某价位时的单价，第二个为此时的销量，以一行-1，-1表示所有已知价位及对应的销量输入完毕，输入的最后一行为一个单独的整数表示在已知的最高单价外每升高一块钱将减少的销量。

输 出

输出有两种情况：若在政府预期价上能得到最大总利润，则输出一个单独的整数，数的正负表示是补贴还是收税，数的大小表示补贴或收税的金额最小值。若有多解，取绝对值最小的输出。

如在政府预期价上不能得到最大总利润，则输出“NO SOLUTION”.

样 例 输入 31 28 130 30 120 31 110 -1 –1 15 输出 4 普及组 题三 乘积最大 （26分） 问题描述 第42页 | 共209页

NOIP 2000 普及组 复赛试题

今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

有一个数字串：312， 当N=3，K=1时会有以下两种分法：

1) 3*12=36 2) 31*2=62

这时，符合题目要求的结果是：31*2=62

现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。 输 入

程序的输入共有两行：

第一行共有2个自然数N，K（6≤N≤40，1≤K≤6） 第二行是一个长度为N的数字串。 输 出

结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。 样 例 输入 4 2 1231 输出 62 普及组 问题描述 第43页 | 共209页

题四． 单词接龙 （36分） NOIP 2000 普及组 复赛试题

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

输 入

输入的第一行为一个单独的整数n(n<=20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输 出

只需输出以此字母开头的最长的“龙”的长度

样 例 ：

输入 5 at touch cheat choose tact a 输出 23

（连成的“龙”为atoucheatactactouchoose）

第44页 | 共209页

NOIP 2000 普及组 测试数据

2000普及组复赛试题测试数据表

题二．税收与补贴问题 (输入)

21．IN 31 28 130 30 120 31 110 -1 –1 15 22．IN 315 280 1300 300 1200 310 1100 -1 –1 150 23．IN 77 74 280 75 266 76 264 77 260 78 239 -1 -1 50 24．IN 4011 1 79990 7999 10 -1 –1 10 题四． 单词接龙 (输入)

41．IN 1 ENVELOPE E 44．IN 8 NO NEW NAME NEVER NATIONAL NECESSARY EVER ME N 42．IN 2 ABABABAB ABABABC A 43．IN 4 ABABABC ABABABD ABABABA CDABAB45．IN 6 ACT TOUCH CHEAT CHOOSE TACT SENCITIVE A 46．IN 6 MANY YOUTH THIS SYSTEM MAIN NAVY M 第45页 | 共209页

NOIP 2000 普及组 测试数据

普 及 组 参 考 答 案 第一题： 计算器的改良

序号 1 2 3 4 5

一元一次方程 20+3x＝－18 －6＋12x＝0 47－2＝6y＋3 －25a＋18－2＝－7a－2 －a+1a－3=a－3 共 １８ 分

输 出 分值 3 4 4 4 3 得分 x＝－12.667 x＝0.500 y＝7.000 a＝1.000 a=0.000 第二题： 税收与补贴问题 共 20 分 序号 1 2 3 4

输 入 内容见21．IN 内容见22．IN 内容见23．IN 内容见24．IN 输 出 4 －32 9 －20 分值 5 5 5 5 得分 第三题： 乘积最大

序号 1 2 3 4

6 1 101010 8 4 321044105 8 3 22222222 10 5 7777777777 输入 共２６分

输出 分值 6 7 6 7 得分 １０１００ ５１６６０００ ２３４２５６ １７２２４９９００９ 第四题： 单词接龙

序号 1 2 3 4 5 6 输 入 内容见41．IN 内容见42．IN 内容见43．IN 内容见44．IN 内容见45．IN 内容见46．IN 共3６分

输出 15 19 43 9 31 38 分值 6 6 6 6 6 6 得分 第46页 | 共209页

NOIP 2000 提高组 复赛试题

提高组复赛试题 （三小时完成 ）

提高组 题一 进制转换 （18分） 问题描述

我们可以用这样的方式来表示一个十进制数： 将每个阿拉伯数字乘以一个以该数字所处位置的（值减１）为指数，以１０为底数的幂之和的形式。例如：１２３可表示为 １＊

２１０

１０＋２＊１０＋３＊１０这样的形式。

与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置的（值－１）为指数，以２为底数的幂之和的形式。一般说来，任何一个正整数Ｒ或一个负整数－Ｒ都可以被选来作为一个数制系统的基数。如果是以Ｒ或－Ｒ为基数，则需要用到的数码为 ０，１，．．．．Ｒ－１。例如，当Ｒ＝７时，所需用到的数码是０，１，２，３，４，５和６，这与其是Ｒ或－Ｒ无关。如果作为基数的数绝对值超过１０，则为了表示这些数码，通常使用英文字母来表示那些大于９的数码。例如对１６进制数来说，用Ａ表示１０，用Ｂ表示１１，用Ｃ表示１２，用Ｄ表示１３，用Ｅ表示１４，用Ｆ表示１５。 在负进制数中是用－Ｒ 作为基数，例如－１５（十进制）相当于１１０００１（－２进制），并且它可以被表示为２的幂级数的和数：

５４３２

１１０００１＝１＊（－２）＋１＊（－２）＋０＊（－２）＋０＊（－２）＋

１０

０＊（－２） ＋１＊（－２）

问题求解 设计一个程序，读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数： －Ｒ?｛－２，－３，－４，．．．，－２０｝ 输 入 输入的每行有两个输入数据。

第一个是十进制数Ｎ（－32768＜＝Ｎ＜＝32767）； 第二个是负进制数的基数－Ｒ。 输 出 结果显示在屏幕上，相对于输入，应输出此负进制数及其基数，若此基数超过１０，则参照１６进制的方式处理。

样 例 输入

３００００ －２ －２００００ －２ ２８８００ －１６ －２５０００ －１６ 输出

３００００＝１１０１１０１０１０１１１００００（ｂａｓｅ －２） －２００００＝１１１１０１１０００１０００００ （ｂａｓｅ －２） ２８０００＝１９１８０ （ｂａｓｅ －１６） －２５０００＝７ＦＢ８ （ｂａｓｅ －１６）

第47页 | 共209页

NOIP 2000 提高组 复赛试题

提高组 题二 乘积最大 （22分）

问题描述

今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

有一个数字串：312， 当N=3，K=1时会有以下两种分法：

1） 3*12=36 2） 31*2=62

这时，符合题目要求的结果是：31*2=62

现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。 输 入

程序的输入共有两行：

第一行共有2个自然数N，K（6≤N≤40，1≤K≤6） 第二行是一个长度为N的数字串。 输 出

结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。 样 例 输入 4 2 1231

第48页 | 共209页

NOIP 2000 提高组 复赛试题

输出 62

提高组

题三． 单词接龙 （27分）

问题描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。

输 入

输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输 出

只需输出以此字母开头的最长的“龙”的长度

样 例 ：

输入 5 at touch cheat choose tact a 输出

23 （连成的“龙”为atoucheatactactouchoose）

第49页 | 共209页

NOIP 2000 提高组 复赛试题

提高组 题四． 方格取数 （33分）

问题描述 设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）： 向右 A 1 2 3 4 5 6 7 8 1 0 0 0 0 0 0 0 0 2 0 0 13 0 0 6 0 0 3 0 0 0 0 7 0 0 0 4 0 0 0 14 0 0 0 0 5 0 21 0 0 0 4 0 0 向 6 0 0 15 0 0 0 0 0 下 7 0 14 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 B

某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B

点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

输 入 输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。

输 出 只需输出一个整数，表示2条路径上取得的最大的和。

样 例 ： 输 入 8

2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4

6 3 15 7 2 14 0 0 0

输 出 67

第50页 | 共209页

本文来源：https://www.bwwdw.com/article/wz1o.html