当前位置:首页 >> 学科竞赛 >>

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> 设有下列的算式: 809 ------------□□) □□□□ □□ ------------□□□ □□□ ------------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 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 B 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

放置的总数为 12 种。 数据输入的方式为: N P1(颜色,为一个字母) N1(灯的数量) P2 N2 ?? Q(结束标记,Q 本身不是灯的颜色) 程序要求:求出一种顺序的排列方案及排列总数。

第 3 页 | 共 209 页

NOIP 1995 普及组 复赛测试数据

NOI’95 “同创杯”全国青少年信息学(计算机)奥林匹克竞赛 分区联赛复赛测试数据(初中组)
<1> 正确算式如下:8 分 12) 9709 96 109 108 1 <2> 本题 18 分(4%+6%+8%) ① 输入 N=1 (4%) 结果: 1 ② 输入 N=3 (6%) 结果: 781 692 543 ③ 输入 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 <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 页

809

① 打印格式占 4% ② 算式不对不给分

B 类=462

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) B=(0,0,0,0,4,5,6)

c 输入:N=7 输出:

A=(3,2,1,0,4,5,6)

<5> 本题共 30 分(10%+10%+10%) ① 数据输入: N=6 P1=R Q 排列方案: 排列总数=6 R R R R R R ② 数据输入:N=6 P1=R P2=Y Q 排列方案: 排列总数=12 R R R R R R R R R R R R Y Y Y Y Y Y N1=2 N2=1 N1=1

第 5 页 | 共 209 页

NOIP 1995 普及组 复赛测试数据

③ 数据输入:N=12 P1=R P2=B P3=Y Q 排列方案: 排列总数: 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 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 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 Y Y Y Y Y Y Y B B B B B B B B B B B B B B B B B B B B Y Y Y Y Y Y Y Y Y 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 B B Y Y Y Y B Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y N1= 3 N2=2 N3=1

第 6 页 | 共 209 页

NOIP 1995 提高组 复赛试题

NOI’95 “同创杯”全国青少年信息学(计算机)奥林匹克竞赛 分区联赛复赛试题(高中组) (上机编程,完成时间:210 分钟)
<1> 编码问题: 设有一个数组 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; 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 中的原数据。 <2> 灯的排列问题: 设在一排上有 N 个格子(N≤20) ,若在格子中放置有不同颜色的灯,每种灯的个数记 为 N1,N2,??Nk(k 表示不同颜色灯的个数) 。 放灯时要遵守下列规则: ③同一种颜色的灯不能分开; ④不同颜色的灯之间至少要有一个空位置。 例如:N=8(格子数) R=2(红灯数) B=3(蓝灯数) 放置的方法有: R-B 顺序 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

第 7 页 | 共 209 页

NOIP 1995 提高组 复赛试题

B-R 顺序 B B B B B B B B B B B B B B 放置的总数为 12 种。 数据输入的方式为: N P1(颜色,为一个字母) N1(灯的数量) P2 N2 ?? Q(结束标记,Q 本身不是灯的颜色) 程序要求:求出一种顺序的排列方案及排列总数。 <3> 设有一个四层的积木块,1~4 层积木块的数量依次为:5,6,7,8 如下图所示放置: B B B B R R R R R R R R R R R R

8 2 3

15 4

8 1

5 4

16 3

9 2

14 6

其中, 给出第三层与第四层所标示的数字, 并已知第三层的数据是由第四层的数据计算 出来的。 计算的方法是:第三层的某个数据 A 是由第四层相邻的两个数据 B,C 经过某种计算 后产生的: A B C

计算所用到的计算符为:+,-, ? ,且无优先级之分(自左向右计算) ,运算符最多为 2 个。 如:3+4 ? 5=35 5 ? 4+3=23 可以看出,上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的: A=B ? C+B 也就是:8=2 ? 3+2,15=3 ? 4+3,??14=2 ? 6+2 程序要求: 给出第四层与第三层的数据后,将第一、二层的每块积木标上相应的数据,并输出整个 完整的积木图及计算公式。 ① 输入数据不存在出错的情况,同时也不会超过整数的范围。
第 8 页 | 共 209 页

NOIP 1995 提高组 复赛试题

② 计算时可允许出现以下情况: A=B (即可理解为运算符的个数为零) A=B ? B+B (即全部由 B 产生)

第 9 页 | 共 209 页

NOIP 1996 普及组 复赛试题

NOI’95 “同创杯”全国青少年信息学(计算机)奥林匹克竞赛 分区联赛复赛测试数据(高中组)
<6> 本题 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%+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)

<7> 本题共 30 分(10%+10%+10%) ④ 数据输入: N=6 P1=R N1=1 Q 排列方案: 排列总数=6 R R R R R ⑤ 数据输入:N=6 P1=R P2=Y Q 排列方案: 排列总数=12 R R R R R R R R R R R R Y Y Y
第 10 页 | 共 209 页

R N1=2 N2=1

Y Y Y

NOIP 1996 普及组 复赛试题

⑥ 数据输入:N=12 P1=R P2=B P3=Y Q 排列方案: R 排列总数: R 105×2=210 R R R R R R R R R R R R R

N1= 3 N2=2 N3=1

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

Y Y Y Y Y Y Y Y Y B B B B B B B B B Y Y Y B B B B B B B B B Y Y Y B B B B Y Y B B Y Y B B B R 3 公式:A=B+C B Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y

B B B B

B B B B B B B

R R R R R R 3 R R R 7 R 4 1 R R R R

B B B

B B B B B B B

R R <8> 本题共 40 分(12%+14%+14%) ① 输入 3 4 4 4 R 4 3R 4 R 2R1 1 2 2 2 2 R 应打印出完整的图形: (12 分) R 15 16 16 15 R 4 7 8 8 8 7 3 4 4 4 4 3 1 2 2 2 2 2

第 11 页 | 共 209 页

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 4 8 4 8 4 2 4 2 4 2 4 2 2 1 2 1 2 1 2 1 8 公式:A=B+B

第 12 页 | 共 209 页

NOIP 1996 普及组 复赛试题

第二届全国青少年信息学(计算机)奥林匹克分区联赛复赛试题 (初中组 竞赛用时:3 小时)
1.编制一个乘法运算的程序(20 分) 从键盘读入 2 个 100 以内的正整数,进行乘法运算并以竖式输出。 例如,输入格式:8913 又如,输入格式:16 8 输出格式: 89 × 13 267 89 1157 输出格式: 16 × 8 128

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 比赛 1==2 1==3 1==4

3 4 3==4 2==4 2==3

一天 二天 三天

第 14 页 | 共 209 页

NOIP 1996 普及组 测试数据

第二届全国青少年信息学(计算机)奥林匹克分区联赛 复赛参考答案(初中组)
题号 1.1 5 1.2 25 40 2 输入 5 ×2 10 25 ×40 00 100 1000 87 ×76 522 609 6612 3 ×78 24 21 234 输出

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

输出 (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)

2.2

2.3

2.4

第 15 页 | 共 209 页

NOIP 1996 普及组 测试数据

j=6

(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. %

题号 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10

原串: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 原串:. 命令:r . % 输入 n=1 n=2

题号 4.1 4.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$=’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.挖地雷(30 分) 在一个地图上有 N 个地窖(N<=20) ,每个地窖中埋有一定数量的地雷。同时,给出地 窖之间的连接路径。 例如:

V1 V5

V

2

V3

V4

[题目要求] 当地窖及其连接的数据给出之后, 某人可以从任一处开始挖地雷, 然后可以沿着指出的 连接往下挖(仅能选择一条路径) ,当无连接时挖地雷工作结束。设计一个挖地雷的方案, 使某人能挖到最多的地雷。 输入格式: N: (表示地窖的个数) W1,W2,W3,……WN (表示每个地窖中埋藏的地雷数量) A12…………… . A1N 地窖之间连接路径(其中Aij=1 表示地窖 i,j A23…………..A2N 之间是否有通路:通 Aij=1,不通 Aij==0) …….. AN-1 N 输出格式:
第 18 页 | 共 209 页

NOIP 1996 提高组 复赛试题

K1--K2--……….KV MAX 例如: ⑩--------⑧

(挖地雷的顺序) (挖地雷的数量)

④-----⑦-------⑥ 输出: 1 –3 -4 max=27

其输入格式为: 5 10,8,4,7,6 1 1 1 0 0 0 0 1 1 1

-5

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 1.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 <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 2.10 题号 3.1 输入 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 61<8>3 输入 n=3 w1=10,w2=20,w3=5 01 0 n=3 w1=5,w2=10,w3=5 11 0 n=6 w1=5,w2=10,w3=20 w4=5,w5=4,w6=5 10100 0100 100 11 1 n=6 w1=10,w2=15,w3=20 w4=15,w5=5, w6=10 00000 0000 000 00 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>=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> 输出

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 1111100000 001100000 10000000 1000000 100000 01000 1100 000 10 1 题号 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.8 4.10 110000 220000 103000 340500 222222 032745 063421 123456 654321 10 10 10 10 1 1 输入 Total=3 Total=6 Total=7 Total=36 Total=82 Total=185 Total=79 Total=204 Total=83 Total=140 输出

第 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<f<i; (2)b<d, g<h, c<e (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 A3 A A7 A4 A1 B(N,M) A5 A2 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

若在 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 输入 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.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 53 6 2 9 8 8 9 4 2 6 7 4 3 5 7 2 5 4 9 6 3 1 8 7 2 6 1 8 9 3 4 5 7

2.2 2.3

P=18 P=19

2.4

P=20

满足条件的方案数:6(如下) 1 2 6 3 6 1 8 7 7 9 5 2 4 9 5 3 4 8 3 4 1 8 9 5 2 6 7 4 3 1 2 7 4 3 9 8 6 1 5 4 2 3
第 25 页 | 共 209 页

NOIP 1997 普及组 测试数据

8 9 5 2 7 6

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

任 2

务 48620



58,980,856,902,730,428,600 任 务 二 118,200.946,737,728,400 2 36,014,973,809,750,037,800

N=30,M=40 (5,5) , (15,15) N=50,M=50 (2,2) , (49,49) N=50,M=50 (2,2) , (7,5)

第 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 11 12 4 15 8 5 7 16 3 14 6 13 10 9 1 2 3 4 6 5 14 15 13 24 23 8 10 19 18 11 9 22 25 12 输入 a+x (((b+c))) a+b(c+a) (a+(b+c) a+)b+c( 任 务 Error Ok Error Error Error 一 (1,1)-(3,2)-(5,1) (6,3) -(7,1)-(8,3)-(9,5) (答案不唯一) 3.2 任 3.3 3.4 3.5 3.6 N=3,M=3 务 二 2 8 NO 3 2 2 1 1 2 11 12 4 9 8 5 7 10 3 14 6 13 16 15 7 1 2 16 6 5 21 13 24 20 10 19 17 9 22 输出 3 4 7 14 15 16 23 8 21 18 11 20 25 12 17 NO 1 4 2 3 输出

1.5

N=5

题号 2.1 2.2 2.3 2.4 2.5 题号 3.1

N=9,M=5

N=30,M=30 (1,15) , (3,15) 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。 3.任何一个正整数都可以用 2 的幂次方表示。例如: 137=2 +2 +2
7 3 0

{30%} {40%}

同时约定方次用括号来表示,即 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 站开出时车上的人数。 2.设有 n 个正整数(n≤20) ,将它们联接成一排,组成一个最大的多位整数。 例如:n=3 时,3 个整数 13,312,343 联接成的最大整数为:34331213 又如:n=4 时,4 个整数 7,13,4,246 联接成的最大整数为:7424613 程序输入:n n 个数 程序输出:联接成的多位数 {40%} {20%}

3.著名科学家卢斯为了检查学生对进位制的理解,他给出了如下的一张加法表,表中的字 母代表数字。 例如: 其含义为: + L K V E L L K V E K K V E KL V V E KL KK E E KL KK KV 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 {40%}

根据这些规则可推导出: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 LM L N=4 +M N P M N MP M N MP MM N PM N P N=6 +M L KN H M L H M MK N L H N L MM MK KM L KN H N MK MM N MH ML H N MK H ML MM N=8 +M N L P QR 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 QM N L P QR S R LQ LS N LL R LP LM S N LP R LQ S LM LL 输出 13 8 138 321121 75422413 3713411331321 4073232121713513 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 1999 普及组 复赛试题

第五届全国青少年信息学(计算机)奥林匹克分区联赛复赛试题 (普及组 竞赛用时:3 小时)

第一题 Cantor 表(30 分) 现代数学的著名证明之一是 George Cantor 证明了有理数是可枚举的。他是用下面这一 张表来证明这一命题的: 1/1 2/1 3/1 4/1 5/1 ? 1/2 2/2 3/2 4/2 ? 1/3 1/4 1/5 ? 2/3 2/4 ? 3/3 ? ? 1/1 2/1 3/1 4/1 5/1 ? 1/2 2/2 3/2 4/2 ? 1/3 1/4 1/5 ? 2/3 2/4 ? 3/3 ? ?

我们以 Z 字形给上表的每一项编号。第 一项是 1/1,然后是 1/2,2/1,3/1,2/2,? 输入:整数 N(1≤N≤10000000) 输出:表中的第 N 项 样例: INPUT OUTPUT N=7 1/4 第二题 回文数(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,求最少经过几步可以得到回 文数。如果在 30 步以内(包含 30 步)不可能得到回文数,则输出“Impossible! ” 样例: INPUT OUTPUT N = 9 M= 87 STEP=6 第三题 旅行家的预算(40 分) 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空 的) 。给定两个城市之间的距离 D1、汽车油箱的容量 C(以升为单位) 、每升汽油能行驶的 距离 D2、出发点每升汽油价格 P 和沿途油站数 N(N 可以为零) ,油站 i 离出发点的距离 Di、每升汽油价格 Pi(i=1,2,?,N) 。计算结果四舍五入至小数点后两位。如果无法到 达目的地,则输出“No Solution” 。 样例: INPUT D1=275.6 C=11.9 D2=27.4 P=2.8 N=2 油站号 I 1 2 OUTPUT 离出发点的距离 Di 102.0 220.0 26.95(该数据表示最小费用) 每升汽油价格 Pi 2.9 2.2

第 36 页 | 共 209 页

NOIP 1999 普及组 测试数据

第五届全国青少年信息学(计算机)奥林匹克分区联赛复赛 (普及组) 测 试 数 据
第一题:共 30 分 序号 1 2 3 4 N 15 85 1999 10278 输出 1/5 7/7 18/46 19/125 分值 5 5 10 10

第二题:共 30 分 序号 1 2 3 4 N 2 16 10 2 M 10011 AC27 89 101111 STEP 4 6 24 Impossible 分值 5 9 10 6

第三题:共 40 分 序号 1 2 输入 D1=99.9 C=15.9 D2=29.8 P=99.9 N=0 D1=199.9 C=9.0 D2=10.0 P=99.9 N=1 100.0 99.9 3 D1=87.75 C=13.03 D2=5.75 P=7.29 N=3 22.10 7.38 24.21 6.81 82.08 6.96 4 D1=475.6 C=11.9 D2=27.4 P=14.98 N=6 102.0 9.99 220.0 13.29 256.3 14.79 275.0 10.29 277.6 11.29 381.8 10.09 192.15 13 105.95 12 输出 334.90 No solution. 分值 10 5

第 37 页 | 共 209 页

NOIP 1999 提高组 复赛试题

第五届全国青少年信息学(计算机)奥林匹克分区联赛复赛试题 (提
第一题 拦截导弹(28 分) 某国为了防御敌国的导弹袭击, 发展出一种导弹拦截系统。 但是这种导弹拦截系统有一 个缺陷: 虽然它的第一发炮弹能够到达任意的高度, 但是以后每一发炮弹都不能高于前一发 的高度。 某天, 雷达捕捉到敌国的导弹来袭。 由于该系统还在试用阶段, 所以只有一套系统, 因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整数) ,计算这套 系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 样例: INPUT 389 207 155 300 299 170 158 65

高 组

竞赛用时:3 小时)

OUTPUT 6(最多能拦截的导弹数) 2(要拦截所有导弹最少要配备的系统数)

第二题 回文数(25 分) 若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。 例如:给定一个 10 进制数 56,将 56 加 65(即把 56 从右向左读) ,得到 121 是一个回 文数。 又如:对于 10 进制数 87: STEP1:87+78 = 165 STEP3:726+627 = 1353

STEP2:165+561 = 726 STEP4:1353+3531 = 4884

在这里的一步是指进行了一次 N 进制的加法,上例最少用了 4 步得到回文数 4884。 写一个程序,给定一个 N(2<=N<=10 或 N=16)进制数 M,求最少经过几步可以得到回文 数。 如果在 30 步以内(包含 30 步)不可能得到回文数,则输出“Impossible! ” 样例: INPUT N = 9 M= 87 第三题 旅行家的预算(27 分) 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空 的) 。给定两个城市之间的距离 D1、汽车油箱的容量 C(以升为单位) 、每升汽油能行驶的距

OUTPUT STEP=6

第 38 页 | 共 209 页

NOIP 1999 提高组 复赛试题

离 D2、出发点每升汽油价格 P 和沿途油站数 N(N 可以为零) ,油站 i 离出发点的距离 Di、 每升汽油价格 Pi(i=1,2,??N) 。计算结果四舍五入至小数点后两位。如果无法到达目 的地,则输出“No Solution” 。 样例: INPUT D1=275.6 C=11.9 D2=27.4 P=2.8 N=2 油站号 I 1 2 离出发点的距离 Di 102.0 220.0 每升汽油价格 Pi 2.9 2.2

OUTPUT 26.95(该数据表示最小费用) 第四题 邮票面值设计(40 分) 给定一个信封,最多只允许粘贴 N 张邮票,计算在给定 K(N+K≤40)种邮票的情况下 (假定所有的邮票数量都足够) ,如何设计邮票的面值,能得到最大值 MAX,使在 1~MAX 之 间的每一个邮资值都能得到。 例如,N=3,K=2,如果面值分别为 1 分、4 分,则在 1 分~6 分之间的每一个邮资值都 能得到(当然还有 8 分、9 分和 12 分) ;如果面值分别为 1 分、3 分,则在 1 分~7 分之间 的每一个邮资值都能得到。可以验证当 N=3,K=2 时,7 分就是可以得到的连续的邮资最大 值,所以 MAX=7,面值分别为 1 分、3 分。 样例: INPUT N=3 K=2

OUTPUT 1 3 MAX=7

第 39 页 | 共 209 页

NOIP 1999 提高组 测试数据

第六届全国青少年信息学(计算机)奥林匹克分区联赛复赛 (提高组) 测 试 数 据
第一题:共 28 分 序 号 1 2 3 4 输入 300 250 275 252 200 138 245 181 205 471 782 1033 1058 1111 465 978 486 476 324 575 384 278 214 657 218 445 123 236 865 858 565 545 445 455 656 844 735 638 652 659 714 845 单枚最大可 击落导弹数 5 1 7 6 需要系统数 2 7 4 7 分值 5 5 10 8

第二题:共 25 分 序号 1 2 3 4 第三题:共 27 分 序号 1 2 3 输入 D1=99.9 C=15.9 D2=29.8 P=99.9 N=0 D1=199.9 C=9.0 D2=10.0 P=99.9 N=1 100.0 99.9 D1=87.75 C=13.03 D2=5.75 P=7.29 N=3 22.10 7.38 24.21 6.81 82.08 6.96 D1=475.6 C=11.9 D2=27.4 P=14.98 N=6 102.0 9.99 220.0 13.29 256.3 14.79 275.0 10.29 277.6 11.29 381.8 10.09 输出 334.90 No solution. 105.95 分值 5 5 7 N 2 16 10 2 M 10011 AC27 89 101111 STEP 4 6 24 Impossible 分值 4 7 9 5

4

192.15

10

第四题:共 40 分 序号 1 2 3 4 N 7 7 10 5 K 3 4 3 5 1 8 13 1 5 24 37 1 10 28 1 4 9 31 51 STEP MAX=69 MAX=165 MAX=146 MAX=126 分值 10 10 10 10

第 40 页 | 共 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 普及组 问题描述
第 42 页 | 共 209 页

题三

乘积最大

(26 分)

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 的数字串。





结果显示在屏幕上,相对于输入,应输出所求得的最大乘积(一个自然数) 。 样 输入 42 1231 输出 62 普及组 例

题四.

单词接龙

(36 分)

问题描述
第 43 页 | 共 209 页

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

(输入)
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

22.IN 315 280 1300 300 1200 310 1100 -1 –1 150

题四.

单词接龙

(输入)
42.IN 2 ABABABA B ABABABC A 43.IN 4 ABABAB C ABABAB D ABABAB A CDABAB A A 46.IN 6 MANY YOUTH THIS SYSTEM MAIN NAVY M

41.IN 1 ENVELOPE E

44.IN 8 NO NEW NAME NEVER NATIONAL NECESSAR Y EVER ME N

45.IN 6 ACT TOUCH CHEAT CHOOSE TACT SENCITIVE A

第 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 输 出 x=-12.667 x=0.500 y=7.000 a=1.000 a=0.000

共 18 分
分值 3 4 4 4 3 得分

第二题:
序号 1 2 3 4 输 内容见 21.IN 内容见 22.IN 内容见 23.IN 内容见 24.IN

税收与补贴问题
入 输 4 -32 9 -20 出 分值 5 5 5 5

共 20 分
得分

第三题:
序号 1 2 3 4 6 1 101010 8 4 321044105 8 3 22222222 10 5 7777777777 输入

乘积最大
输出 10100 5166000 234256 1722499009 分值 6 7 6 7

共26分
得分

第四题:
序号 1 2 3 4 5 6 输 内容见 41.IN 内容见 42.IN 内容见 43.IN 内容见 44.IN 内容见 45.IN 内容见 46.IN 入

单词接龙
输出 15 19 43 9 31 38 分值 6 6 6 6 6 6

共 36分
得分

第 46 页 | 共 209 页

NOIP 2000 提高组 复赛试题

提高组复赛试题 (三小时完成 ) 提高组
问题描述 我们可以用这样的方式来表示一个十进制数: 将每个阿拉伯数字乘以一个以该数字所 处位置的(值减1)为指数,以10为底数的幂之和的形式。例如:123可表示为 1* 2 1 0 10 +2*10 +3*10 这样的形式。 与之相似的,对二进制数来说,也可表示成每个二进制数码乘以一个以该数字所处位 置的(值-1)为指数,以2为底数的幂之和的形式。一般说来,任何一个正整数R或一个 负整数-R都可以被选来作为一个数制系统的基数。 如果是以R或-R为基数, 则需要用到 的数码为 0,1, . . . .R-1。例如,当R=7时,所需用到的数码是0,1,2,3, 4,5和6,这与其是R或-R无关。如果作为基数的数绝对值超过10,则为了表示这些 数码, 通常使用英文字母来表示那些大于9的数码。 例如对16进制数来说, 用A表示10, 用B表示11,用C表示12,用D表示13,用E表示14,用F表示15。 在负进制数中是用-R 作为基数, 例如-15 (十进制) 相当于110001 (-2进制) , 并且它可以被表示为2的幂级数的和数: 5 4 3 2 110001=1*(-2) +1*(-2) +0*(-2) +0*(-2) + 1 0 0*(-2) +1*(-2) 问题求解 设计一个程序,读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负 进制下的数: -R?{-2,-3,-4, . . . ,-20} 输 入 输入的每行有两个输入数据。 第一个是十进制数N(-32768<=N<=32767) ; 第二个是负进制数的基数-R。 输 出 结果显示在屏幕上,相对于输入,应输出此负进制数及其基数,若此基数超过10,则 参照16进制的方式处理。 样 例 输入 30000 -2 -20000 -2 28800 -16 -25000 -16 输出 30000=11011010101110000(base -2) -20000=1111011000100000 (base -2) 28000=19180 (base -16) -25000=7FB8 (base -16)

题一

进制转换

(18 分)

第 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 0 0 0 0 0 0 0 1 0 0 0 0 21 0 14 0 2 0 0 13 0 0 0 15 0 0 3 4 0 0 0 14 0 0 0 0 5 0 0 7 0 0 0 0 0 6 0 6 0 0 4 0 0 0 向右 7 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B

某人从图的左上角的 A 点出发,可以向下行走,也可以向右走,直到到达右下角的 B 点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字 0) 。 此人从 A 点到 B 点共走两次,试找出 2 条这样的路径,使得取得的数之和为最大。 输 入 输入的第一行为一个整数 N(表示 N*N 的方格图) ,接下来的每行有三个整数,前两个 表示位置,第三个数为该位置上所放的数。一行单独的 0 表示输入结束。 输 出 只需输出一个整数,表示 2 条路径上取得的最大的和。 样 例 输 入 8 2 3 2 6 3 5 4 4 5 2 5 6 6 3 7 2 0 0 :

13 6 7 14 21 4 15 14 0

输 出 67

第 50 页 | 共 209 页

NOIP 2000 提高组 测试数据






单词接龙











题三.

测试数据(输入)
32.IN 2 ABABABA B ABABABC A 33.IN 4 ABABAB C ABABAB D ABABAB A CDABAB A .IN 36 A 6 MANY YOUTH THIS SYSTEM MAIN NAVY M

31.IN 1 ENVELOPE E

34.IN 8 NO NEW NAME NEVER NATIONAL NECESSAR Y EVER ME N

35.IN 6 ACT TOUCH CHEAT CHOOSE TACT SENCITIVE A

题四.

方格取数 测试数据(输入)
42.IN 9 1 2 10 1 3 7 1 4 4 3 4 3 4 3 6 5 1 5 5 3 7 5 5 3 0 0 0 43.IN 7 1 3 2 1 4 3 2 3 3 3 3 3 5 5 4 6 5 4 7 3 2 7 5 4 0 0 0 44.IN 8 1 1 13 1 3 7 1 8 14 2 2 1 2 4 2 4 3 5 5 5 4 6 2 6 7 8 16 0 0 0 45.IN 8 1 1 1 1 8 1 2 2 2 2 7 2 3 4 3 3 5 3 4 4 3 4 5 3 7 2 2 7 7 2 8 1 1 8 8 1 0 0 0

41.IN 3 1 1 10 1 3 5 2 2 6 2 3 4 3 1 8 3 2 2 0 0 0

第 51 页 | 共 209 页

NOIP 2000 提高组 测试数据


第一题:
序号 1 2 3 4 5 27993 -37336 -569 -304 683 输












共 18 分

进制转换
入 -8 -16 -2 -20 -2 输 出 72651 AFE8 1011011011 GG 11111111111 3 4 4 3 4

分值

得分

第二题:
序号 1 2 3 4 6 1 101010 9 4 321044105 8 3 22222222 10 5 7777777777 输 入

乘积最大
输 出 10100 5166000 234256 1722499009 分 值 4 6 5 7

共 22 分
得分

第三题:
序号 1 2 3 4 5 6 输 内容见 31.IN 内容见 32.IN 内容见 33.IN 内容见 34.IN 内容见 35.IN 内容见 36.IN 入

单词接龙
输出 15 19 43 9 31 38 分值 3 3 4 5 7 5

共 27 分
得分

第四题:
序号 1 2 3 4 5 输 入

方格取数
输 30 40 25 60 18 出 内容见 41.IN 内容见 42.IN 内容见 43.IN 内容见 44.IN 内容见 45.IN 5 6 7 7 8

共 33 分
分值 得分

第 52 页 | 共 209 页

NOIP 2001 普及组 复赛试题

NOI’2001 第七届全国青少年信息学(计算机)奥林匹克分区联 赛复赛试题 普及组
题一 数的计算(20 分) 问题描述 我们要求找出具有下列性质数的个数(包含输入的自然数 n): 先输入一个自然数 n(n<=1000),然后对此自然数按照如下方法进行处理: 1. 不作任何处理; 2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半; 3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止. 样例: 输入: 6 满足条件的数为 6 (此部分不必输出) 16 26 126 36 136 输出: 6 题二 最大公约数和最小公倍数问题(20 分) 问题描述 输入二个正整数 x0,y0(2<=x0<100000,2<=y0<=1000000), 求出满足下列条件 的 P,Q 的个数 条件: 1.P,A 是正整数 2.要求 P,Q 以 x0 为最大公约数,以 y0 为最小公倍数. 试求:满足条件的所有可能的两个正整数的个数. 样例 输入:x0=3 yo=60 输出:4 说明(不用输出)此时的 P Q 分别为: 3 60 15 12 12 15 60 3 所以:满足条件的所有可能的两个正整数的个数共 4 种.

题三 求先序排列(30 分) 问题描述

第 53 页 | 共 209 页

NOIP 2001 普及组 复赛试题

给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不 同的大写字母表示,长度<=8)。 样例 输入:BADC BDCA 输出:ABCD 题四 装箱问题(30 分) 问题描述 有一个箱子容量为 V(正整数,0<=V<=20000),同时有 n 个物品 (0<n<=30=,每个物品有一个体积(正整数)。 要求 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。 样例 输入: 24 一个整数,表示箱子容量 6 一个整数,表示有 n 个物品 8 接下来 n 行,分别表示这 n 个物品的各自体积 3 12 7 9 7 输出: 0 一个整数,表示箱子剩余空间。

第 54 页 | 共 209 页

NOIP 2001 提高组 复赛试题

2001 年全国青少年信息学(计算机)奥林匹克分区联赛复赛试题 (高中组 竞赛用时:3 小时)

题一 一元三次方程求解(20 分) 问题描述 有形如: ax3+bx2+cx+d=0 这样的一个一元三次方程。 给出该方程中各项的系数(a, b, c, d 均为实数),并约定该方程存在三个不同实根(根的范围在-100 至 100 之间),且根与 根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空 格),并精确到小数点后 2 位。 提示:记方程 f(x)=0,若存在 2 个数 x1 和 x2,且 x1<x2,f(x1)*f(x2)<0,则在(x1, x2)之间一定有一个 根。 样例 输入:1 -5 输出:-2.00

-4 2.00

20 5.00

题二 数的划分(20 分) 问题描述 将整数 n 分成 k 份,且每份不能为空,任意两份不能相同(不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; 1,5,1; 5,1,1; 问有多少种不同的分法。 输入:n,k (6<n<=200,2<=k<=6) 输出:一个整数,即不同的分法。 样例 输入: 7 3 输出:4 {四种分法为:1,1,5;1,2,4;1,3,3;2,2,3;}

题三 统计单词个数(30 分) 问题描述 给出一个长度不超过 200 的由小写英文字母组成的字母串(约定;该字串以每行 20 个字母的方式输入,且 保证每行一定为 20 个)。 要求将此字母串分成 k 份(1<k<=40), 且每份中包含的单词个数加起来总数最大(每 份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串 this 中可包 含 this 和 is,选用 this 之后就不能包含 th)。 单词在给出的一个不超过 6 个单词的字典中。 要求输出最大的个数。 输入格式 去部输入数据放在文本文件 input3.dat 中,其格式如下: 第一行为一个正整数(0<n<=5)表示有 n 组测试数据 每组的第一行有二个正整数(p,k)
第 55 页 | 共 209 页

NOIP 2001 提高组 复赛试题

p 表示字串的行数; k 表示分为 k 个部分。 接下来的 p 行,每行均有 20 个字符。 再接下来有一个正整数 s,表示字典中单词个数。(1<=s<=6) 接下来的 s 行,每行均有一个单词。 输出格式 结果输出至屏幕,每行一个整数,分别对应每组测试数据的相应结果。 样例 输入: 1 1 3 thisisabookyouareaoh 4 is a ok sab 输出: //说明:(不必输出) 7 // this/isabookyoua/reaoh

题四 Car 的旅行路线(30 分) 问题描述 又到暑假了,住在城市 A 的 Car 想和朋友一起去城市 B 旅游。她知道每个城市都有四个飞机场,分别位于 一个矩形的四个顶点上,同一个城市中两个机场之间有一条笔直的高速铁路,第 I 个城市中高速铁路了的 单位里程价格为 Ti,任意两个不同城市的机场之间均有航线,所有航线单位里程的价格均为 t。 ?图例暂不可用,请谅解? 那么 Car 应如何安排到城市 B 的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题,于是她 来向你请教。 任务 找出一条从城市 A 到 B 的旅游路线,出发和到达城市中的机场可以任意选取,要求总的花费最少。 输入文件:键盘输入文件名 输 出:到屏幕(输出最小费用,小数点后保留 1 位。) 输入格式 第一行为一个正整数 n(0<=n<=10),表示有 n 组测试数据。 每组的第一行有四个正整数 s,t,A,B。 S(0<S<=100)表示城市的个数,t 表示飞机单位里程的价格,A,B 分别为城市 A,B 的序号,(1<=A,B<=S)。 接下来有 S 行,其中第 I 行均有 7 个正整数 xi1,yi1,xi2,yi2,xi3,yi3,Ti,这当中的(xi1,yi1), (xi2,yi2),(xi3,yi3)分别是第 I 个城市中任意三个机场的坐标,T I 为第 I 个城市高速铁路单位里程 的价格。 输出格式

第 56 页 | 共 209 页

NOIP 2001 提高组 复赛试题

共有 n 行,每行一个数据对应测试数据。 样例 输入 1 1 10 1 3 1 1 1 3 3 1 30 2 5 7 4 5 2 1 8 6 8 8 11 6 3 输出: 47.55

第 57 页 | 共 209 页

NOIP 2001 提高组 解题报告&测试数据

第七届(2001)分区联赛复赛解题报告(提高组)
感谢原作者?俞玮、赵爽

第一题:一元三次方程求解
给出一个三次方程 f ( x) ? ax3 ? bx2 ? cx ? d ? 0 ,试求它所有的三个根。这里所有的根都 在区间 [?100,100] 中,并保证方程具有三个实根,且它们之间的差不小于 1。

分析:
如果是一般的求三次方程根的问题,那么只能直接使用求根公式,但这是非常复杂的。 由于题目要求只精确到 0.01,故我们考虑一下是否可以应用数值方法进行计算。由题目给 出的方程在区间内存在根的条件可知,我们可以用一个变量 i 从-100.000 到 100.000 以 步长 0.001 做循环。若 f (i) ? f (i ? 0.001) ? 0 ,则可知在区间 (i, i ? 0.001) 内存在方程的 解。这样无论这个区间内的解是什么,在取两位小数的精度后都与 i 取两位小数的结果是一 样的。故我们就可以把取两位小数精度的 i 作为问题的解。另外还有可能方程的根在区间端 点 i 的情况,我们可以通过判断 f (i ) 是否为 0 来获得。 但这种方法由于用到了题目所要求的数值精度小的特殊性, 故无法扩展。 而在用数值方法求 方程根的时候, 我们最常用的方法就是二分法。 该方法的应用在于如果确定了方程 f ( x) ? 0 在区间 ( a, b) 内如果存在且只存在一个根,那么我们可以用逐次缩小根可能存在范围的方法 确定出根的某精度的数值。该方法主要利用的就是题目所给的若在区间 ( a, b) 内存在一个方 程的根,则 f (a) ? f (b) ? 0 这个事实,并重复执行如下的过程: ? ? ? 取当前可能存在解的区间 ( a, b) ; 若 a ? 0.001 ? b 或 f 若 f (a) ? f
b ,则可确定根为 ? a? 2 ??0

a?b 并退出过程; 2

b b b , 则由题目给出的定理可知根在区间 ? a, a ? 中, 故对区间 ? a, a ? ? a? 2 ??0 2 ? 2 ?

重复该过程; ? 若 f (a) ? f
b b b ,则必然有 f ? a? ,也就是说根在 ? a? 中,应该对 ? a? 2 ??0 2 ? ? f (b) ? 0 2 , b?

第 58 页 | 共 209 页

NOIP 2001 提高组 解题报告&测试数据

此区间重复该过程。 最后,就可以得到精确到 0.001 的根。 再考虑什么样的区间内会有根1。由于题目给出了所有的根都在-100 到 100 之间,且 根与根之间差不小于 1 的限制条件,故我们可知,在 [?100, ?99) 、 [?99, ?98) 、……、

[99,100) 、 [100,100] 这 201 个区间内,每个区间内至多只能存在一个根。这样对除去区
间 [100,100] 外2的其他的区间 [a, a ? 1) ,要么 f (a) ? 0 ,要么 f (a) ? f (a ? 1) ? 0 时这个方 程在此区间内才有解。若 f (a) ? 0 ,显然 a 为解;若 f (a) ? f (a ? 1) ? 0 ,则可以利用上面 所说的方法球出解来。这样就可求出这个方程的所有解。 最后是输出的解要求排序。 我们既可以在求出来之后排序, 也可以从小到大的顺序求解, 就可以按照升序求出所有解。

数据:
输入 1 2 3 4 1 -2 -1 2 1 -4.65 2.25 1.4 1 10 -1 -10 1 -1.8 -8.59 -0.84 输出 -1.00 1.00 2.00 -0.35 1.00 4.00 -10.00 -1.00 1.00 -2.10 -0.10 4.00

第二题:数的划分
求把一个整数 n 无序划分成 k 份互不相同的正整数之和的方法总数。

分析:
这是一道整数剖分的问题。这类问题的数学性很强,方法也很多。这里介绍一种较为巧 妙的办法。 我们不必拘泥于原问题如何求解, 而把思维转换一个角度来考虑一个与原问题等价的问 题。 我们可以形象的把 n 的 k-自然数剖分看作把 n 块积木堆成 k 列,且每列的积木个数依 次递增,也就是这 n 块积木被从左到右积木被堆成了“楼梯状” 。比如,下图是 10 的几种 4-剖分。

1 2

更确切地说是只有一个根。 该区间显然只有一个数,可以用用判断 f (100) 是否为 0 的方法来求出该区间内方程的根。对此,我们特 殊处理。
第 59 页 | 共 209 页

NOIP 2001 提高组 解题报告&测试数据

现在,我们不妨把这三个图顺时针旋转 90 度,成为3:

不难发现,旋转之后的模型还是 10 的剖分,不过约束条件有所不同。很明显,由于原 来是 k 剖分,因此新的模型中最大的一个元素必然是 k。而其余的元素大小不限,但都不能 大于 k。因此问题转化成了求 n 的任意无序剖分,其中最大的元素是 k4。当然,我们可以 把 n 减去 k,成为 n? ,剩下的问题就是求 n? 的任意剖分,且其中每个元素都不大于 k 的方 案总数了。 求解这个新的模型可以用递推的方法。用 f ?a, b ? 表示把 b 做任意剖分,其中最大的一 个部分恰好是 a 的方案总数。用 g ?a, b ? 表示把 b 做任意剖分,其中最大的一个部分不大于 a 的方案总数。那么,有:

? f ?a, b ? ? g ?a, b ? a ? ? a 。 ? ? ? ? ? g a , b ? f i , b ? ? i ?1 ?
消去 f ,有: g ?a, b ? ?

? f ?i, b? ? ? g ?i, b ? i ? ? g ?a ? 1, b? ? g ?a, b ? a ? 。我们可以
i ?1 i ?1

a

a

按照 a 、 b 递增的顺序计算 g ( a, b) 的值,这样在在计算 g ?a, b ? 的时候, g ?a ? 1, b? 和

g ?a, b ? a ? 都 已 经 得 到 , 故 我 们 只 用 进 行 一 次 简 单 的 加 法 运 算 即 可 。 最 后 的 g ?n, k ?? ? g ?k , n ? k ? 即为所求。
3 4

该图为数学上的一个著名图示(Ferrer 图) ,对此有兴趣的读者可以自己参看一些数学书。 由于篇幅有限,这里就不严格证明这两个问题的等价性了。
第 60 页 | 共 209 页

NOIP 2001 提高组 解题报告&测试数据

这 种 方 法的 时 间复 杂 度为 O ?

? ?2n? ? k ? 1?k ? ? ?2n ? 3k ? 1?k ? 。 空 间复 杂 度为 ? O? ? ? 2 2 ? ? ? ?

O(nk),或者我们可以用滚动数组的方法降到 O(n)。 该题中模型转化的思想,是很值得借鉴的。

数据:
输入 1 2 3 4 5 72 20 4 100 5 200 5 200 6 3 64 38225 583464 4132096 输出

第三题:统计单词个数
给出一个长度不超过 200 的由小写英文字母组成的字符串 (约定: 该字符串以每行 20 个字母的方式输入,且保证每行一定 20 个) 。要求将此字符串分成 k 份(1<k≤40) ,且每 份中包含的单词个数加起来最大(每份中包含的单词可以重叠。当选用一个单词之后,其第 一个字母不能再用。例如字符串 this 中可以包含 this 和 is,但是选用 this 之后就不能再 选 th) 。

分析:
这一题应该算是一道比较原创的题目。 注意到题目中有一个非常特殊的地方, 就是以串 中某个位置的字母为首字母,最多只能分出一个单词。由于在拆分字符串的过程中,如果以 某位置为首某个较短单词被截断, 那么以该位置为首的较长单词必然也会被截断。 也就是说, 对于各个位置来说我们选取较短的单词总不会比选取较长的单词所形成的单词少。 这样我们 可以定义一个在位置 i 的参数 mlen[i] 表示以位置 i 的字母为首字母, 所能形成的最短单词的 长度。 这样如果在这个位置加上这个单词的长度之内截断, 则以该位置为首字母就不能形成 5 6 单词,否则就可能形成一个单词 。这样对于所有的不同 l 个首位置,我们只要在各个位置 依次对各个单词进行匹配就以得出所对应的 mlen 的值,这一部分的复杂度为 O(wl2)7。然 后是计算把字串分为多个部分的过程中有什么单词可以留下。由于是把字串分为多个部分, 故我们类比其他的分割字串的问题,列出动态规划的方程如下:

f [l , k ] ? max ? f [l ? i, k ? 1] ? g[l ? i ? 1, i ]?
1?i ?l ?1

5 6 7

当然前提是在这个位置可以匹配上一个单词。 这里 l 为该字串的长度。 这里 w 为单词的个数。
第 61 页 | 共 209 页

NOIP 2001 提高组 解题报告&测试数据

这里有初值 f [l ,1] 为:

f [l ,1] ? g[1, l ]
这个式子中, f [ l , k ] 表示把字串前 l 个字符分成 k 段时所形成的最多单词的数目,

g[ p, i ] 表示字串的第 p 个字符开始的 i 个字符形成的字串中所能形成的单词数。这里 g[ p, i ] 由于过于庞大,不能用预计算的方法加快速度,只能现用现算。计算的方法为对于
所有 p ? q ? p ? i ?1 的 q ,如果 mlen[q] 存在(也就是有单词可以在位置 q 匹配上) ,且

q ? mlen[q] ? 1 ? p ? i ? 1 ,则该位置必然可以匹配上一个单词。把所有这样位置的数目加
起来就可以得到 g[ p, i ] 的值了。这样算法的复杂度为 O(kl3)。 但这里计算还有一个技巧, 就是我们可以依次按照 k 增加,l 增加,i 增加的顺序计算 f 的值。这样在 i 由 i ' 增加到 i '? 1 的时候,由于在计算 i '? 1 所对应的 g 值时可以用

g[ p ? 1, i '? 1] ? g[ p, i '] ? 1 p ? 1 ? mlen[ p ? 1] ? 1 ? p ? i '? 1 ? g[ p, i '] p ? 1 ? mlen[ p ? 1] ? 1 ? p ? i '? 1
这个方程进行复杂度为 O(1)的递推计算,故总复杂度可以降到 O(kl2+wl2)。 这种被称作双重动态规划的方法,请读者自己好好体会。

数据:
输入 21 thisisappleisthisthe oopbooktheisurrtoywe 4 is of the book 44 dfhfghgdfksgdflsdsds sdsdsddfsdffssddsfdf asasassasdsdsdsdsdsd sadadadasdsdsdsdssdd 4 输出

1

8

2

13

第 62 页 | 共 209 页

NOIP 2001 提高组 解题报告&测试数据

dssd dfdfdf sdsd jkjjk 10 4 aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa 1 aaaaa 10 4 sdfsdsassdasdddsasdd sdasdsasdsadasdasdsa assasaasadassadsaadd ssasdasdasdssddsassa asdasdasdasdasddsads dsadasdasdasadssdssa asssdasdsasdassdssaa dsaddsasdasdsadsaasa adsadsasddsadsadsssa adsdsaasddsaadsdsasa 6 aa sa ds da sa sd 10 4 sdfsdsassdasdddsasdd sdasddassdsaadaasdsa assasaasadassadsaadd ssasdsaasdassddsassa saddssassasdsaasssds dsasdasdsddasdasdssa asssdasdsasdassdssaa sadsassdssassdsasssa
第 63 页 | 共 209 页

3

193

4

125

5

65

NOIP 2001 提高组 解题报告&测试数据

sasdsasdsasdsasdsssa sdsasdsasdsassdasdsa 6 asd dsa ads das sad sda

第四题:CAR 的旅行路线
又到暑假了,住在城市 A 的 Car 想和朋友一起去城市 B 旅游。她知道每个城市都有四 个飞机场, 分别位于一个矩形的四个顶点上, 同一个城市的两个机场之间有一条笔直的高速 铁路,第 i 个城市高速铁路的单位里程价格为 Ti。任意两个不同城市的机场之间均有航线, 所有航线单位里程的价格均为 t。 那么 Car 应如何安排到 B 的路线才能尽可能的节省花费呢?她发现这并不是一个简单 的问题,于是她来向你请教。

分析:
我们换一种对题目描述的方法, 就是给出一张地图, 求出某人从某点到另一点的最短距 离。这是一个图论中的标准问题,就是在一个无向图中求最短路径的问题。 首先, 这个人在从起点到终点所可能停下的点都是确定的, 就是一个城市的四个机场 (其 他的时候是没有更换交通工具的自由的) 。所以我们可以以所有的机场为顶点,而机场与机 8 场之间的交通路线 为边建立一个图。该图的边权值为机场之间相互通行所需的时间。至于 求最短路,我们可以使用一个被称为 Dijkstra 的算法。该算法的主要思想就是模拟液体等 速的在管子内流动,先流到的位置就是离起点较近的位置。在使用算法实现的时候,我们可 以把顶点划分为已流到的和未流到的两个部分。 依次找出液体从已流到的部分最少还需经过 多少时间才能流到未流到的部分,并模拟流的过程。有关该算法的具体内容,请读者自行参 见有关图论的算法书籍,这里不赘述。 最后, 还需注意的是题目中对于一个城市只给出了三个机场的坐标。 但我们知道这四个 机场是成矩形排列的, 而矩形的对角线互相平分。 故我们可以先找出这三个机场中相对的两 个机场, 易知这样的机场就是距离最大的两个机场。 然后通过对这两个机场求平均数求出该 矩形的中心, 再把另一个机场按矩形的中心作对称就可以得出第四个机场的坐标。 还有题目 中最多可能有 400 个节点,也就是说可能有 80000 条边。这些边显然是无法事先计算并 保存下来的。但由于在求最短路径的过程中,每一条边最多只会访问两遍,故我们可以采用 现用现算的办法。 其他在计算点与点之间距离时也要注意对整数取平方时的运算有可能引发 整数越界的问题,我们应该先转换成实数再进行计算。 该算法的时间复杂度为 O?

?3 2? n ? ,空间复杂度为 O(n)。 ?2 ?

8

可能为铁路或航线。
第 64 页 | 共 209 页

NOIP 2001 提高组 解题报告&测试数据

数据:
输入 1 1 1 10 1 1 1 1 2 2 2 1 10 1 3 10 1 3 2 2 2 1 1 2 10 2 12 12 2 22 12 1 22 22 22 32 32 22 10 1 3 10 1 3 10 1 1 10 1 1 10 20 1 30 1 30 111 1 10 110 10 111 1 111 10 1 10 10 1 2 27 27 194 105 194 27 10 366 290 381 290 366 305 10 80 158 196 245 196 158 1 289 154 358 154 358 86 2 17 284 84 350 84 284 1 175 289 292 289 175 362 3 450 371 420 371 420 32 2 241 29 270 29 270 43 4 251 182 347 270 251 270 5 347 341 410 341 347 369 1 1 15 50 1 15 1231437 1 12 3 11 4 13 36 1 22 3 21 4 23 5 1 32 3 31 4 33 19 1 42 3 41 4 43 47 11 2 13 1 14 3 2 11 12 13 11 14 13 11 22 13 21 14 23 11 32 13 31 14 33 11 42 13 41 14 43 21 2 23 1 24 3 34 21 12 23 11 24 13 21 22 23 21 24 23 输出 0.00

2

214.14

3

310.00

4

1885.03

5

1924.23 6 1 27 29 16 14
第 65 页 | 共 209 页

NOIP 2001 提高组 解题报告&测试数据

21 32 23 31 24 33 41 21 42 23 41 24 43 3

关于 yuwei 和 zhaoshuang 的报告的一点补充 第一题: 其实最简单的方法是这样子的: 让 x 从 –100.00 到 100.00 枚举一下, 得到 20000 个 f(x) , 取跟 0 最接近的三个 f(x),对应的 x 就是答案了。 (提示有时候会扰乱别人的 思维) 第二题:如果时间不是很严格的话,枚举还是能过的。 第三题:这跟我在分区赛前出的一道模拟试题方法类似。不过分区这题的数据巨弱,居然只 输出”有多少个位置开始至少可以有一个单词”也能对 4/5 的点!真是佩服出数据的人?? 第四题:标准算法的题目,不过这题算老题目了?? 算费用的时候,令 A,B 城市内的路费 为 0 的话,就可以直接得到结果,而不需要做 4 遍 Dijkstra。

第 66 页 | 共 209 页

NOIP 2002 普及组 复赛试题

2002 年全国青少年信息学(计算机)奥林匹克分区联赛复赛试题 (普及组 竞赛用时:3 小时) 题一 级数求和(存盘名:NOIPC1) [问题描述]: 已知:Sn= 1+1/2+1/3+?+1/n。显然对于任意一个整数 K,当 n 足够大的时候,Sn 大于 K。 现给出一个整数 K(1<=k<=15),要求计算出一个最小的 n;使得 Sn>K。 [输入] 键盘输入 k [输出] 屏幕输出 n [输入输出样例] 输人:1 输出:2

题二 选数(存盘名:NOIPC2) [问题描述]: 已知 n 个整数 x1,x2,?,xn,以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。 例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时,可得全部的组合与它们的和为: 3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。 现在,要求你计算出和为素数共有多少种。 例如上例,只有一种的和为素数:3+7+19=29)。 [输入]: 键盘输入,格式为: n , k (1<=n<=20,k<n) x1,x2,?,xn (1<=xi<=5000000) [输出]: 屏幕输出,格式为: 一个整数(满足条件的种数)。 [输入输出样例]: 输入: 4 3 3 7 12 19 输出: 1 题三 产生数(存盘名:NOIPC3) [问题描述]: 给出一个整数 n(n<10^30) 和 k 个变换规则(k<=15)。
第 67 页 | 共 209 页

NOIP 2002 普及组 复赛试题

规则: 一位数可变换成另一个一位数: 规则的右部不能为零。 例如:n=234。有规则(k=2): 2-> 5 3-> 6 上面的整数 234 经过变换后可能产生出的整数为(包括原数): 234 534 264 564 共 4 种不同的产生数 问题: 给出一个整数 n 和 k 个规则。 求出: 经过任意次的变换(0 次或多次),能产生出多少个不同整数。 仅要求输出个数。 [输入]: 键盘输人,格式为: n k x1 y1 x2 y2 ... ... xn yn [输出]: 屏幕输出,格式为: 一个整数(满足条件的个数): [输入输出样例]: 输入: 234 2 2 5 3 6 输出: 4 题四 过河卒(存盘名:NOIPC4) [问题描述]: 如图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方 的马(如上图的 C 点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个 点(图中的 P1,P2 ? P8 和 C)。卒不能通过对方马的控制点。

第 68 页 | 共 209 页

NOIP 2002 普及组 复赛试题

棋盘用坐标表示,A 点(0,0)、B 点(n,m)(n,m 为不超过 20 的整数,并由键盘输入),同样马的位置坐标是需要给 出的(约定: C<>A,同时 C<>B)。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。 [输入]: 键盘输入 B 点的坐标(n,m)以及对方马的坐标(X,Y){不用盘错} [输出]: 屏幕输出 一个整数(路径的条数)。 [输入输出样例]: 输入: 6 6 3 2 输出: 17

第 69 页 | 共 209 页

NOIP 2002 普及组 解题报告

NOIp2002 普及组解题报告
感谢原作者?湖南赛区 黄艺海

题一: 级数求和
[问题描述]: 已知:Sn=1+1/2+1/3+…+1/n。显然对于任意一个整数 K,当 n 足够大的时候,Sn 大于 K。现给出一个整数 K(1<=K<=15) ,要求计算出一个最小的 n,使得 Sn>K [问题分析]: 这道题目非常简单,题目的意思已经把该题的算法描述得再清楚不过了,初始时 Sn=0,n=0,然后每次循环 n?n+1,Sn?Sn+1/n,,直到 Sn 大于 K,最后输出 K。另外实型(Real 是最慢的,建议用 Extended)的运算速度不是很快,而 K 为 1~15 之间的整数,所以最后可 以交一张表(常量数组) ,以达到最好的效果 [参考程序] program c1; var K: Byte; n: Longint; Sn: Extended; begin Readln(K); Sn := 0; n := 0; Repeat Inc(n); Sn := Sn + 1 / n; Until Sn > k; Writeln(n); end.

题二: 选数
[问题描述]: 已知 n(1<=n<=20)个整数 x1,x2,…,xn(1<=xi<=5000000) ,以及一个整数 k(k<n) 。 从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。现在,要求你计算出和为素数共 有多少种。 [问题分析]: 本题动态规划无从下手,也无数学公式可寻,看来只能搜索(组合的生成算法) ,其实 1<=n<=20 这个约束条件也暗示我们本题搜索是有希望的, 组合的生成可用简单的 DFS 来实

第 70 页 | 共 209 页

NOIP 2002 普及组 解题报告

现,既搜索这 k 个整数在原数列中的位置,由于组合不同于排列,与这 k 个数的排列顺序无 关,所以我们可以令 a[I]<a[I+1](a[I]表示第 I 个数在原数列中的位置) ,这个组合生成算法 的复杂度大约为 C(n,k),下面给出递归搜索算法的框架: Proc Search(dep) Begin for i <- a[dep - 1] + 1 to N - (M - dep) do 1:a[dep] <- i 2:S <- S + x[i] 3:if dep < k then Search(dep + 1) else 判断素数 4:S <- S - x[i] End

接下来的问题就是判断素数,判断一个整数 P(P>1)是否为素数最简单的方法就是看是否存 在一个素数 a(a<=sqrt(P)) 是 P 的约数,如果不存在,该数就为素数,由于在此题中 1<=xi<=5000000,n<=20,所以要判断的数 P 不会超过 100000000,sqrt(p)<=10000,因此,为 了加快速度,我们可以用筛选法将 2…10000 之间的素数保存到一个数组里(共 1229 个) , 这样速度估计将提高 5~6 倍。 特别注意:本题是要求使和为素数的情况有多少种,并不是求有多少种素数,比赛时就 有很多同学胡乱判重而丢了 12 分;还有 1 不是素数,在判素数时要对 1 做特殊处理。 [参考程序] program c2; const MaxN = 20; var N, M, i: Byte; ans, s: Longint; x: array[1 .. MaxN] of Longint; f: array[1 .. 10000] of Byte; p: array[1 .. 1229] of Integer; procedure Get_Prime; var i, j, s: Integer; begin s := 0; f[1] := 0; for i := 2 to 10000 do f[i] := 1; for i := 2 to 10000 do
第 71 页 | 共 209 页

NOIP 2002 普及组 解题报告

if f[i] = 1 then begin Inc(s); p[s] := i; j := 2 * i; while j <= 10000 do begin f[j] := 0; Inc(j, i) end; end end;

题三: 产生数
[问题描述]: 给出一个整数 n(n<10^30)和 k 个变换规则(k<=15) 。 规则: 1 个数字可以变换成另一个数字 规则的右部不能为零。 问题: 给出一个整数 n 和 k 个规则 求出: 经过任意次的变换(0 次或多次) ,能产生出多少个不同的整数。 [问题分析]: 认真分析题目之后发现,本题搜索显然是不行的,而且对于只需计数而不需求具体方 案的题目,一般都不会用搜索解决,其实本题不难看出,可以用乘法原理直接进行计数,用 Fi 表示数字 i 包括本身可以变成的数字总个数 (这里的变成可以是直接变成也可以是间接变 成,比如 3->5,5->7,那么 3->7) ,那么对于一个数 a(用数组存,长度为 n) ,根据乘法原理它 能产生出 F[a[1]]*F[a[2]]*F[a[3]]*…F[a[n]]个不同整数,相信这一点大家不难理解。那么现 在的关键就是如何求 Fi,由于这些变换规则都是反应的数字与数字之间的关系,这很容易 让我们想到用图来表示这种关系: 1: 建立一个有向图 G,初始化 g[i, j] ? False 2: 如果数字 i 能直接变成数字 j,那么 g[i, j] ? True 容易知如果数字 i 能变成数字 j,那么 i 到 j 必须存在路径,否则 i 是不可能变成 j 的,这样 一来,Fi 的求解就显得非常简单了,求一个顶点 v 包括本身能到达的顶点数的方法相当多, 可以用 BFS,DFS,Dijkstra,Floyd,这里介绍一种类似 Floyd 的有向图的传递闭包算法,该算 法实现简单 ,在解决这类问题时比 Floyd 效率更高,所谓有向图的传递闭包就是指可达性 矩阵 A=[a[i, j]],其中 a[i, j] = True 从 i 到 j 存在通路 a[i, j] = False 从 i 到 j 不存在通路 所以有向图传递闭包算法只需将 floyd 算法中的算术运算符操作‘+’用相应的逻辑运算符 ‘and’和’or’代替就可以了,其算法如下: for k ? 1 to n do for i ? 1 to n do

第 72 页 | 共 209 页

NOIP 2002 普及组 解题报告

for j ? 1 to n do a[i, j] = a[i, j] or (a[i, k] and a[k, j]) 最后值得注意的是当 n 很大时输出可能会超过 Comp 类型的范围,所以要使用高精度乘法, 由于高精度算法是信息学竞赛中的基础,这里就不在详述。 [参考程序] program c3; const MaxLen = 30; var Len, M: Byte; a: array[1 .. MaxLen] of Byte; f: array[0 .. 9] of Byte; g: array[0 .. 9, 0 .. 9] of Boolean; procedure Init; var i: Byte; St: String; begin Readln(st); Len := 0; M := 0; i := 1; while st[i] in ['0' .. '9'] do begin Inc(Len); a[Len] := Ord(st[i]) - 48; Inc(i) end; Repeat if st[i] in ['0' .. '9'] then M := M * 10 + Ord(st[i]) - 48; Inc(i) Until i > Length(st) end; procedure Main; var i, j, k: Byte; begin Fillchar(g, Sizeof(g), False); for k := 1 to M do begin Readln(i, j); g[i, j] := True end; for k := 0 to 9 do

第 73 页 | 共 209 页

NOIP 2002 普及组 解题报告

for i := 0 to 9 do for j := 0 to 9 do g[i, j] := g[i, j] or (g[i, k] and g[k, j]); Fillchar(f, Sizeof(f), 0); for i := 0 to 9 do g[i, i] := True; for i := 0 to 9 do for j := 0 to 9 do Inc(f[i], Ord(g[i, j])) end; procedure Show; var i, j, k, g: Byte; ans: Array[1 .. MaxLen] of Byte; begin Fillchar(ans, Sizeof(ans), 0); ans[1] := 1; for k := 1 to Len do begin g := 0; for i := 1 to MaxLen do begin ans[i] := ans[i] * f[a[k]] + g; g := ans[i] div 10; ans[i] := ans[i] mod 10 end end; j := MaxLen; While ans[j] = 0 do Dec(j); for i := j downto 1 do Write(ans[i]); Writeln; end; begin Init; Main; Show; end.

题四: 过河卒
[问题描述]: 棋盘上 A 点有一个过河卒,需要走到目标 B 点。卒行走的规则:可以向下、或者向右。 同时在棋盘上 C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方

第 74 页 | 共 209 页

NOIP 2002 普及组 解题报告

马的控制点。 棋盘用坐标表示,A 点(0,0)、B 点(n, m) (n,m 为不超过 20 的整数),同样马的位置坐 标是需要给出的。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数 [问题分析]: 这是一道老得不能再老的题目了,很多书上都有类似的题目,NOIp97 普及组的最后一 题就和本题几乎一模一样。有些同学由于没见过与之类似的题目,在比赛时用了搜索,当 n 到 14,15 左右就会超时,其实,本题稍加分析,就能发现:要到达棋盘上的一个点,只能 从左边过来或是从上面下来,所以根据加法原理,到达某一点的路径数目,等于到达其相邻 上,左两点的路径数目之和,因此我们可以使用逐列(或逐行)递推的方法来求出从起始顶 点到重点的路径数目,即使有障碍(我们将马的控制点称为障碍) ,这一方法也完全适用, 只要将到达该点的路径数目置为 0 即可,用 F[i,j]表示到达点(i,j)的路径数目,g[i,j]表 示点(i, j)有无障碍,递推方程如下:

F[0,0] F[i,j] F[i,0] F[0,j] F[i,j]

= = = = =

1 0 F[i-1,0] F[0,j-1] F[i-1,j] + F[i,j-1]

{ g[x,y] = 1 } {i > 0, g[x,y] = 0} {j > 0, g[x,y] = 0} {i > 0, j > 0, g[x, y] = 0}

本题与第三题一样,也要考虑精度问题,当 n,m 都很大时,可能会超过 MaxLongInt,所以要 使用 Comp 类型计数(Comp 类型已经足够了, 即使 n=20,m=20, 没有任何障碍的情况下的结果 也只有 14,5 位的样子)。 [参考程序]

program c4; const dx: array[1 .. 8] of Shortint = (-2, -1, 1, 2, 2, 1, -1, -2); dy: array[1 .. 8] of Shortint = (1, 2, 2, 1, -1, -2, -2, -1); var n, m, x, y, i, j: Byte; g: array[0 .. 20, 0 .. 20] of Byte; f: array[0 .. 20, 0 .. 20] of Comp; begin Readln(n, m, x, y); Fillchar(g, Sizeof(g), 0); g[x, y] := 1; for i := 1 to 8 do if (x + dx[i] >= 0) and (x + dx[i] <= n) and (y + dy[i] >= 0) and (y + dy[i] <= m) then g[x + dx[i], y + dy[i]] := 1;

第 75 页 | 共 209 页

NOIP 2002 普及组 解题报告

f[0, 0] := 1; for i := 1 to n do if g[i, 0] = 0 then f[i, 0] := f[i - 1, 0]; for i := 1 to m do if g[0, i] = 0 then f[0, i] := f[0, i - 1]; for i := 1 to n do for j := 1 to m do if g[i, j] = 0 then f[i, j] := f[i - 1, j] + f[i, j - 1]; Writeln(f[n, m]: 0: 0) end.

总结:
四道题目其实都很容易,要想到正确可行的方法并不难,考察的是大家的编程基础,一些 基本算法的简单应用,并不需要什么优化技巧,关键是看大家对这些基本算法是否已熟练掌 握,只有熟练掌握这些算法 ,在考试中才能在较短的时间内做好每道题 ,我们一定要重视基 础!

注意:原作者及本人皆不能保证参考程序的准确与严密!

第 76 页 | 共 209 页

NOIP 2002 提高组 复赛试题

2002 年全国青少年信息学(计算机)奥林匹克分区联赛复赛试题 (提高组 竞赛用时:3 小时)

题一 均分纸牌(存盘名 NOIPG1) [问题描述] 有 N 堆纸牌,编号分别为 1,2,?, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可 以在任一堆上取若于张纸牌,然后移动。 移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上 取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。 现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。 例如 N=4,4 堆纸牌数分别为: ① 9 ② 8 ③ 17 ④ 6 移动 3 次可达到目的: 从 ③ 取 4 张牌放到 ④ (9 8 13 10) -> 从 ③ 取 3 张牌放到 ②(9 11 10 10)-> 从 ② 取 1 张牌放到①(10 10 10 10)。 [输 入]: 键盘输入文件名。文件格式: N(N 堆纸牌,1 <= N <= 100) A1 A2 ? An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000) [输 出]: 输出至屏幕。格式为: 所有堆均达到相等时的最少移动次数。‘ [输入输出样例] a.in: 4 9 8 17 6 屏慕显示: 3
题二 字串变换 (存盘名: NOIPG2) [问题描述]: 已知有两个字串 A$, B$ 及一组字串变换的规则(至多 6 个规则): A1$ -> B1$ A2$ -> B2$ 规则的含义为:在 A$中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ ?。 例如:A$='abcd' B$='xyz' 变换规则为: ‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’ 则此时,A$ 可以经过一系列的变换变为 B$,其变换的过程为:

第 77 页 | 共 209 页

NOIP 2002 提高组 复赛试题

‘abcd’->‘xud’->‘xy’->‘xyz’ 共进行了三次变换,使得 A$ 变换为 B$。 [输入]: 键盘输人文件名。文件格式如下: A$ B$ A1$ B1$ \ A2$ B2$ ... ... / 所有字符串长度的上限为 20。 [输出]: 输出至屏幕。格式如下: 若在 10 步(包含 10 步)以内能将 A$ 变换为 B$ ,则输出最少的变换步数;否则输出"NO ANSWER!" [输入输出样例] b.in: abcd wyz abc xu ud y y yz 屏幕显示: 3 |-> 变换规则

题三 自由落体(存盘名:NOIPG3) [问题描述]: 在高为 H 的天花板上有 n 个小球,体积不计,位置分别为 0,1,2,?.n-1。在地面上有一个小车(长为 L, 高为 K,距原点距离为 S1)。已知小球下落距离计算公式为 d=1/2*g*(t^2),其中 g=10,t 为下落时间。地面上 的小车以速度 V 前进。 如下图:

第 78 页 | 共 209 页

NOIP 2002 提高组 复赛试题

小车与所有小球同时开始运动,当小球距小车的距离 <= 0.00001 时,即认为小球被小车接受(小球落到地面 后不能被接受)。 请你计算出小车能接受到多少个小球。 [输入]: 键盘输人: H,S1,V,L,K,n (l<=H,S1,V,L,K,n <=100000) [输出]: 屏幕输出: 小车能接受到的小球个数。 [输入输出样例] [输入]: 5.0 9.0 5.0 2.5 1.8 5 [输出]: 1 题四 矩形覆盖(存盘名 NOIPG4) [问题描述]: 在平面上有 n 个点(n <= 50),每个点用一对整数坐标表示。例如:当 n=4 时,4 个点的坐标分另为:p1 (1,1),p2(2,2),p3(3,6),P4(0,7),见图一。

第 79 页 | 共 209 页

NOIP 2002 提高组 复赛试题

这些点可以用 k 个矩形 (1<=k<=4) 全部覆盖, 矩形的边平行于坐标轴。 当 k=2 时, 可用如图二的两个矩形 sl, s2 覆盖,s1,s2 面积和为 4。问题是当 n 个点坐标和 k 给出后,怎样才能使得覆盖所有点的 k 个矩形的面积之 和为最小呢。约定:覆盖一个点的矩形面积为 0;覆盖平行于坐标轴直线上点的矩形面积也为 0。各个矩形必须完全 分开(边线与顶点也都不能重合)。 [输入]: 键盘输人文件名。文件格式为 n k xl y1 x2 y2 ... ... xn yn (0<=xi,yi<=500) [输出]: 输出至屏幕。格式为: 一个整数,即满足条件的最小的矩形面积之和。 [输入输出样例] d.in : 4 2 1 1 2 2 3 6 0 7 屏幕显示: 4

第 80 页 | 共 209 页

NOIP 2002 提高组 解题报告

2002 年全国青少年信息学(计算机) 奥林匹克分区联赛复赛提高组试题解题报告

本人未经原作者允许即引用,并非用于商业用途,在这里表示歉意 二次引用请注明出处~,切勿用于盈利及其它~

题一 均分纸牌(存盘名 NOIPG1) [问题描述] 有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必 为 N 的倍数。可以在任一堆上取若干张纸牌,然后移动。 移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编 号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌, 可以移到相邻左边或右边的堆上。 现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。 例如 N=4,4 堆纸牌数分别为: ① 9 ② 8 ③ 17 ④ 6 移动 3 次可达到目的: 从 ③ 取 4 张牌放到 ④ (9 8 13 10) -> 从 ③ 取 3 张牌放到 ②(9 11 10 10)-> 从 ② 取 1 张牌放到①(10 10 10 10) 。 [输 入]: 键盘输入文件名。文件格式: N(N 堆纸牌,1 <= N <= 100) A1 A2 … An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000) [输 出]: 输出至屏幕。格式为: 所有堆均达到相等时的最少移动次数。‘ [输入输出样例] a.in: 4 9 8 17 6 屏幕显示: 3 分析:如果你想到把每堆牌的张数减去平均张数,题目就变成移动正数,加到负 数中,使大家都变成 0,那就意味着成功了一半!拿例题来说,平均张数为 10, 原张数 9,8,17,6,变为-1,-2,7,-4,其中没有为 0 的数,我们从左边出发: 要使第 1 堆的牌数-1 变为 0,只须将-1 张牌移到它的右边(第 2 堆)-2 中;结果 是-1 变为 0,-2 变为-3,各堆牌张数变为 0,-3,7,-4;同理:要使第 2 堆变为
第 81 页 | 共 209 页

NOIP 2002 提高组 解题报告

0,只需将-3 移到它的右边(第 3 堆)中去,各堆牌张数变为 0,0,4,-4;要 使第 3 堆变为 0,只需将第 3 堆中的 4 移到它的右边(第 4 堆)中去,结果为 0, 0,0,0,完成任务。每移动 1 次牌,步数加 1。也许你要问,负数张牌怎么移, 不违反题意吗?其实从第 i 堆移动-m 张牌到第 i+1 堆, 等价于从第 i+1 堆移动 m 张牌到第 i 堆,步数是一样的。 如果张数中本来就有为 0 的,怎么办呢?如 0,-1,-5,6,还是从左算起(从右 算起也完全一样) ,第 1 堆是 0,无需移牌,余下与上相同;再比如-1,-2,3, 10,-4,-6,从左算起,第 1 次移动的结果为 0,-3,3,10,-4,-6;第 2 次移 动的结果为 0,0,0,10,-4,-6,现在第 3 堆已经变为 0 了,可节省 1 步,余 下继续。 程序清单 program NOIPG1; const maxn=100; var i,j,n,step:integer;ave:longint; a:array[1..maxn]of integer; f:text;filename:string; begin write('Input filename:');readln(filename); assign(f,filename);reset(f); readln(f,n);ave:=0;step:=0; for i:=1 to n do begin read(f,a[i]); inc(ave,a[i]); end; ave:=ave div i; for i:=1 to n do a[i]:=a[i]-ave; i:=1;j:=n; while a[i]=0 do inc(i);{过滤左边的 0} while a[j]=0 do dec(j);{过滤右边的 0} while (i<j) do begin inc(a[i+1],a[i]);{将第 i 堆牌移到第 i+1 堆中去} a[i]:=0;{第 i 堆牌移走后变为 0} inc(step);{移牌步数计数} inc(i);{对下一堆牌进行循环操作} while a[i]=0 do inc(i);{过滤移牌过程中产生的 0} end; writeln(step); end. 点评:基本题(较易) 本题有 3 点比较关键:一是善于将每堆牌数减去平均数, 简化了问题;二是要过滤掉 0(不是所有的 0,如-2,3,0,-1 中的 0 是不能过 滤的) ;三是负数张牌也可以移动,这是辩证法(关键中的关键) 。

第 82 页 | 共 209 页

NOIP 2002 提高组 解题报告

题二 字串变换 (存盘名: NOIPG2) [问题描述]: 已知有两个字串 A$, B$ 及一组字串变换的规则(至多 6 个规则): A1$ -> B1$ A2$ -> B2$ 规则的含义为:在 A$中的子串 A1$ 可以变换为 B1$ 、A2$ 可以变换为 B2$ ?。 例如:A$='abcd' B$='xyz' 变换规则为: ‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’ 则此时,A$ 可以经过一系列的变换变为 B$,其变换的过程为: ‘abcd’->‘xud’->‘xy’->‘xyz’ 共进行了三次变换,使得 A$ 变换为 B$。 [输入]: 键盘输人文件名。文件格式如下: A$ B$ A1$ B1$ \ A2$ B2$ |-> 变换规则 ... ... / 所有字符串长度的上限为 20。 [输出]: 输出至屏幕。格式如下: 若在 10 步(包含 10 步)以内能将 A$ 变换为 B$ ,则输出最少的变换步 数;否则输出"NO ANSWER!" [输入输出样例] b.in: abcd xyz abc xu ud y y yz 屏幕显示: 3 分析:本题是典型的广度优先搜索的例子,但如果只采用正向搜索,某些情况下计算量过
大,速度过慢,故采取双向搜索且判重并适当剪枝,效果较好。

程序清单
{$A-,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-,Y-} {$M 8192,0,655360} program NOIPG2; const maxn=2300; type node=record{定义节点数据类型} str:string[115];dep:byte; end; {str 表示字串,其长度不会超过 115(长度超过 115 的字串

第 83 页 | 共 209 页

NOIP 2002 提高组 解题报告

不可能通过变换成为目标字串,因为题目限定变换 10 次之内,且串长 不超过 20,即起始串最多可经过 5 次变换时增长,中间串的最大长度 为 20+5*19=115,否则经过余下的步数不可能变为长度不超过 20 的 目标串),dep 表示深度} ctype=array[1..maxn]of ^node; bin=0..1; var maxk:byte;c:array [0..1]of ctype; x0:array[0..6,0..1]of string[20]; filename:string; open,closed:array [0..1] of integer; procedure Init;{读取数据,初始化} var f:text;temp:string;i,j:integer; begin for i:=0 to 1 do for j:=1 to maxn do new(c[i,j]); write('Input filename:');readln(filename); assign(f,filename);reset(f);i:=0; while not eof(f) and (i<=6) do begin readln(f,temp); x0[i,0]:=copy(temp,1,pos(' ',temp)-1); x0[i,1]:=copy(temp,pos(' ',temp)+1,length(temp)); inc(i); end; maxk:=i-1;close(f); end; procedure calc; var i,j,k:integer;st:bin; d:string;f:text; procedure bool(st:bin);{判断是否到达目标状态或双向搜索相遇} var i:integer; begin if x0[0,1-st]=c[st,closed[st]]^.str then begin {如果到达目标状态,则输出结果,退出} writeln(c[st,closed[st]]^.dep); halt; end; for i:=1 to closed[1-st] do if c[st,closed[st]]^.str=c[1-st,i]^.str then begin {如果双向搜索相遇(即得到同一节点), 则输出结果(2 个方向搜索的步数之和),退出} writeln(c[st,closed[st]]^.dep+c[1-st,i]^.dep); halt; end;

第 84 页 | 共 209 页

NOIP 2002 提高组 解题报告

end; procedure checkup(st:bin);{判断节点是否与前面重复} var i:integer; begin for i:=1 to closed[st]-1 do if c[st,i]^.str=c[st,closed[st]]^.str then begin dec(closed[st]);exit;{如果节点重复,则删除本节点} end; bool(st);{如果节点不重复,再判断是否到达目标状态} end; procedure expand(st:bin);{扩展产生新节点} var i,j,k,lx,ld:integer; begin inc(open[st]);d:=c[st,open[st]]^.str;{队首节点出队} k:=c[st,open[st]]^.dep;ld:=length(d); for i:=1 to maxk do begin {从队首节点(父节点)出发产生新节点(子节点)} lx:=length(x0[i,st]); for j:=1 to ld do begin if (copy(d,j,lx)=x0[i,st]) and (length(copy(d,1,j-1)+x0[i,1-st] +copy(d,j+lx,ld))<=115) then begin {如果新节点的串长超过 115,则不扩展!即剪掉此枝} if closed[st]>=maxn then exit;{如果队列已满,只好退出} inc(closed[st]);{新节点入队} c[st,closed[st]]^.str:=copy(d,1,j-1)+x0[i,1-st]+copy(d,j+lx,ld); c[st,closed[st]]^.dep:=k+1;{子节点深度=父节点深度+1} checkup(st);{检查新节点是否重复} end; end; end; end; Begin for st:=0 to 1 do begin{正向(st=0)逆向(st=1)搜索节点队列初始化} open[st]:=0;closed[st]:=1; c[st,closed[st]]^.str:=x0[0,st];c[st,closed[st]]^.dep:=0; bool(st); end; repeat {选择节点数较少且队列未空、未满、深度未达到 10 的方向先扩展} if (open[0]<=open[1]) and not ((open[0]>=closed[0]) or (closed[0]>=maxn) or (c[0,closed[0]]^.dep>10)) then expand(0); if (open[1]<=open[0]) and not ((open[1]>=closed[1]) or (closed[1]>=maxn) or (c[1,closed[1]]^.dep>10)) then expand(1); {如果一方搜索终止,继续另一方的搜索,直到两个方向都终止}

第 85 页 | 共 209 页

NOIP 2002 提高组 解题报告

if not ((open[0]>=closed[0]) or (closed[0]>=maxn) or (c[0,closed[0]]^.dep>10)) then expand(0); if not ((open[1]>=closed[1]) or (closed[1]>=maxn) or (c[1,closed[1]]^.dep>10)) then expand(1); until (open[0]>=closed[0]) or (c[0,closed[0]]^.dep>10) or (closed[0]>=maxn) and (closed[1]>=maxn) or (open[1]>=closed[1]) or (c[1,closed[1]]^.dep>10); {终止条件:任一方队空(无解)或搜索深度超过 10(10 步内无解) 或双方均溢出(可能有解也可能无解,应尽量避免,要尽量把节 点数组开大一点,采用双向搜索,采取剪枝措施等)} End; BEGIN init; calc; writeln('NO ANSWER!') END.

点评:基本题(较难) 考察队列、(双向)广度优先搜索算法及字符串的运算, 基本上可以考察出参赛者的数据结构和算法水平。

第 86 页 | 共 209 页

NOIP 2002 提高组 解题报告

题三 自由落体(存盘名:NOIPG3) [问题描述]: 在高为 H 的天花板上有 n 个小球, 体积不计, 位置分别为 0, 1, 2, ?. n-1。 在地面上有一个小车(长为 L,高为 K,距原点距离为 S1)。已知小球下落距 离计算公式为 d=1/2*g*(t^2),其中 g=10,t 为下落时间。地面上的小车以速 度 V 前进。 如下图:

小车与所有小球同时开始运动,当小球距小车的距离 <= 0.00001 时,即认 为小球被小车接受(小球落到地面后不能被接受)。 请你计算出小车能接受到多少个小球。 [输入]: 键盘输人: H,S1,V,L,K,n (l<=H,S1,V,L,K,n <=100000) [输出]: 屏幕输出: 小车能接受到的小球个数。 [输入输出样例] [输入]: 5.0 9.0 5.0 2.5 1.8 5 [输出]: 1 分析:显然,小车太慢(即 V<=Vmin)或太快(V>Vmax)时,一个球也接不到。 即在 V<=Vmin 或 V>Vmax 时输出为 0。 下面分别求 Vmin 和 Vmax。 当第 n-1 个小球 落地的瞬间, 小车在小球的右端离小球尚有 e=0.00001 的距离, 小车的这个极小 速度就是 Vmin。小车从天花板落到地面的时间 t1=

2H ,这段时间内小车走了 g

S1-(n-1)-e,所以 Vmin=

S1 ? (n ? 1) ? e 。当第 1 个小球落到距小车的上表面为 t1

e 的瞬间,小车在小球的左端离小球距离为 e,小车的这个极大速度就是 Vmax。

第 87 页 | 共 209 页

NOIP 2002 提高组 解题报告

小球从天花板落到离小车上表面为 e 的距离的时间为 t2=

2( H ? K ? e) ,小车移 g

动的距离为 S1+L+e,所以 Vmax=

S1 ? L ? e 。 t2

那么,当 Vmin<V<=Vmax 时,就可接到球了。显然,时间段[t2,t1]是小车接球的 时间,在 t2 时刻,小车的位置为:左表面离原点距离为 S1-V*t2,右表面离原点 距离为 S1-V*t2+L;在 t1 时刻,小车的位置为:左表面离原点距离为 S1-V*t1, 右表面离原点距离为 S1-V*t1+L;故小车的接球范围(在小车运动范围外扩展 e) 为[S1-V*t1-e,S1-V*t2+L+e],球的个数就等于接球范围内所包含的 0~n-1 之间 的整数的个数. 程序清单 program NOIPG3; const g=10{重力加速度};e=1E-5;{小车接受小球的极限距离} var H,s1,v,l,k,t1,t2,Vmin,Vmax:real; n2,n1,num,n:integer; begin readln(h,s1,v,l,k,n);num:=-1; t1:=sqrt(2*h/g);{小球落地时间} if h<=k+e then t2:=0 else t2:=sqrt(2*(h-k-e)/g);{小球落到小车上的 最短时间} if s1-v*t2+L+e<0 then num:=0 else n2:=trunc(s1-v*t2+L+e);{小车接受的球的最大编号为 n2} if n2>n-1 then n2:=n-1;{n2 取 trunc(s1-v*t2+L+e)与 n-1 的较小值} if s1-v*t1-e<=0 then n1:=0 else if s1-v*t1-e>n-1 then num:=0 else if (s1-v*t1-e)=trunc(s1-v*t1-e) then n1:=trunc(s1-v*t1-e){小车接受的球的最小编号 为 n1} else n1:=trunc(s1-v*t1-e)+1; if num=-1 then num:=n2-n1+1;{小车接受的球的个数为 num} writeln(num); end. 点评:送分题 本题“物理味”有余而“信息味”不足,连循环语句都用不上! 难见的“送分题”,可物理较差的人也得不到多少分哦!

第 88 页 | 共 209 页

NOIP 2002 提高组 解题报告

题四 矩形覆盖(存盘名 NOIPG4) [问题描述]: 在平面上有 n 个点(n <= 50),每个点用一对整数坐标表示。例如:当 n =4 时,4 个点的坐标分另为:p1(1,1),p2(2,2),p3(3,6),P4(0, 7),见图一。

这些点可以用 k 个矩形(1<=k<=4)全部覆盖,矩形的边平行于坐标轴。当 k=2 时,可用如图二的两个矩形 sl,s2 覆盖,s1,s2 面积和为 4。问题是当 n 个点坐标和 k 给出后, 怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小 呢。约定:覆盖一个点的矩形面积为 0;覆盖平行于坐标轴直线上点的矩形面积 也为 0。各个矩形必须完全分开(边线与顶点也都不能重合)。 [输入]: 键盘输人文件名。文件格式为 n k xl y1 x2 y2 ... ... xn yn (0<=xi,yi<=500) [输出]: 输出至屏幕。格式为: 一个整数,即满足条件的最小的矩形面积之和。 [输入输出样例] d.in : 4 2 1 1 2 2 3 6 0 7 屏幕显示: 4

分析 1、本题的难度较大。如果你这样认为:即在假定已用 i 个矩形(面积和满足最 小)覆盖所有点的基础上,穷举所有 2 个矩形合并成 1 个矩形(条件是:在所有
第 89 页 | 共 209 页

NOIP 2002 提高组 解题报告

合并方案中使合并后面积最小) ,从而使矩形个数减少为 i-1——那就错了,可是 却可以通过前 4 组测试数据! 正确的做法是对不同的 K 值分别进行计算,好在 K 值较小,否则... 讨论: k=1,只要求出 n 个点坐标的最大、最小值,就可求得矩形的位置与面积; k=2,有 2 个矩形,它们只有 2 种分布形式:左右式(flag=0) ,上下式(flag=1)
1 2 2 1 flag=0 flag=1

对于左右式,显然要先将所有点按横坐标升序排列,可将点 1~点 i-1 放入矩形 1 中,将点 i~点 n 放入矩形 2 中,求两矩形的面积之和;如果面积和比上一个值 小,记下;让 i 从 2 循环到 n,就可完成左右式的全部搜索; 对于上下式,先将所有点按纵坐标升序排列,依此类推。 k=3,有 3 个矩形,它们有 6 种分布形式:
3 1 2 3 2 1 flag=0 flag=1 1 3 2 flag=2

2 1 flag=3

3 3 1 2 flag=4

2 1

3

flag=5

要用两重循环进行搜索:设 i,j 为循环变量,将点 1~i-1 放入矩形 1 中,点 i~j-1 放入矩形 2 中,点 j~n 放入矩形 3 中;点必须在放入前排好序(均为升序) :对 于 flag=0,所有点按横坐标排序;对于 flag=1,所有点按纵坐标排序;对于 flag=2,所有点先 按横坐标排序,然后点 i~n 按纵坐标排序;对于 flag=3,所有点先按横坐标排序,然后点 1~j-1 按纵坐标排序;对于 flag=4,所有点先按纵坐标排序,然后点 1~j-1 按横坐标排序; 对于 flag=5,所有点先按纵坐标排序,然后点 i~n 按横坐标排序; 至于 k=4,4 个矩形有 22 种分布形式,实在太复杂!幸好测试数据中没有 K=4 的 情形(似乎有意放了一马?)。据说本题全国没有一人全对! (只要求 K=1,2,3) 程序清单 {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+,Y+} {$M 65520,0,655360} program NOIPG4; const maxn=50;maxk=3; type rect=record{定义"矩形"数据类型}
第 90 页 | 共 209 页

NOIP 2002 提高组 解题报告

l,r,t,b:word;{矩形的左边,右边,下边,上边距坐标轴的距离} end; vxy=record{定义"点"数据类型} x,y:word;{点的横、纵坐标} end; var ju:array[1..maxk]of rect; v:array[1..maxn,0..2] of vxy;v0:vxy; n,k,i,j,ii,jj:byte;f:text;filename:string; Smin,temp:longint; function intersect(jui,juj:rect):boolean;{判断两矩形是否有公共点} var b1,b2,t1,t2,l1,l2,r1,r2:word; begin b1:=jui.b;b2:=juj.b;t1:=jui.t;t2:=juj.t; l1:=jui.l;l2:=juj.l;r1:=jui.r;r2:=juj.r; intersect:=((l2<=r1) and (l2>=l1) or (r2<=r1) and (r2>=l1) or (l2<=l1) and (r2>=r1)) and ((t2<=b1) and (t2>=t1) or (b2<=b1) and (b2>=t1) or (b2>=b1) and (t2<=t1)); end; function area(ju:rect):longint;{求矩形的面积} var temp:longint; begin temp:=ju.b-ju.t;area:=temp*(ju.r-ju.l); {不能直接写成 area:=(ju.b-ju.t)*(ju.r-ju.l);因为这样可能会溢出!} end; procedure insert(v:vxy;var ju:rect);{将点放入矩形} begin if v.x<ju.l then ju.l:=v.x; if v.x>ju.r then ju.r:=v.x; if v.y<ju.t then ju.t:=v.y; if v.y>ju.b then ju.b:=v.y; end; procedure init;{初始化} begin write('Input filename:');readln(filename); assign(f,filename);reset(f);readln(f,n,k); for i:=1 to n do begin read(f,v[i,0].x,v[i,0].y); v[i,1].x:=v[i,0].x;v[i,1].y:=v[i,0].y; end; for i:=1 to n-1 do{按横坐标升序排列各点,存入 v[i,0]} for j:=i+1 to n do if v[i,0].x>v[j,0].x then begin v0:=v[i,0];v[i,0]:=v[j,0];v[j,0]:=v0; end;
第 91 页 | 共 209 页

NOIP 2002 提高组 解题报告

for i:=1 to n-1 do{按纵坐标升序排列各点,存入 v[i,1]} for j:=i+1 to n do if v[i,1].y>v[j,1].y then begin v0:=v[i,1];v[i,1]:=v[j,1];v[j,1]:=v0; end; end; procedure solve;{核心计算} begin smin:=maxlongint; case k of 1:begin{K=1 的情形} ju[1].b:=v[n,1].y;ju[1].t:=v[1,1].y; ju[1].r:=v[n,0].x;ju[1].l:=v[1,0].x; smin:=area(ju[1]); end; 2:for jj:=0 to 1 do begin{K=2 的情形} {flag=0,1 的情形} ju[1].b:=v[1,jj].y;ju[1].t:=v[1,jj].y; ju[1].r:=v[1,jj].x;ju[1].l:=v[1,jj].x; for i:=2 to n do begin insert(v[i-1,jj],ju[1]);{将第 i-1 点放入矩形 1} ju[2].b:=v[i,jj].y;ju[2].t:=v[i,jj].y;{将第 i 至 n 点放入矩形 2} ju[2].r:=v[i,jj].x;ju[2].l:=v[i,jj].x; for ii:=i+1 to n do insert(v[ii,jj],ju[2]); if not intersect(ju[1],ju[2]) then begin{如果两矩形不交叉} temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]); if temp<smin then smin:=temp; end; end; end; 3:begin for jj:=0 to 1 do begin {flag=0,1 的情形} ju[1].b:=v[1,jj].y;ju[1].t:=v[1,jj].y; ju[1].r:=v[1,jj].x;ju[1].l:=v[1,jj].x; for i:=2 to n-1 do begin insert(v[i-1,jj],ju[1]); ju[2].b:=v[i,jj].y;ju[2].t:=v[i,jj].y; ju[2].r:=v[i,jj].x;ju[2].l:=v[i,jj].x; if intersect(ju[1],ju[2]) then continue; for j:=i+1 to n do begin insert(v[j-1,jj],ju[2]); ju[3].b:=v[j,jj].y;ju[3].t:=v[j,jj].y; ju[3].r:=v[j,jj].x;ju[3].l:=v[j,jj].x; for ii:=j+1 to n do insert(v[ii,jj],ju[3]);
第 92 页 | 共 209 页

NOIP 2002 提高组 解题报告

if intersect(ju[2],ju[3]) then continue; temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]); if temp<smin then smin:=temp; end; end; end; {flag=2 的情形:先竖直划分大矩形;再在右矩形中水平划分} ju[1].b:=v[1,0].y;ju[1].t:=v[1,0].y; ju[1].r:=v[1,0].x;ju[1].l:=v[1,0].x; for i:=2 to n-1 do begin for ii:=1 to n do v[ii,2]:=v[ii,0];{所有点按横坐标升序排列,存入 v[i,2]} for ii:=i to n-1 do{将点 i 至 n 按纵坐标升序排列,存入 v[i,2]} for jj:=ii+1 to n do if v[ii,2].y>v[jj,2].y then begin v0:=v[ii,2];v[ii,2]:=v[jj,2];v[jj,2]:=v0; end;{结果: 所有点先按横坐标升序排列, 然后点 i 至 n 按纵坐 标升序排列} insert(v[i-1,2],ju[1]);{将第 i-1 点放入矩形 1} ju[2].b:=v[i,2].y;ju[2].t:=v[i,2].y;{将第 i 点放入矩形 2} ju[2].r:=v[i,2].x;ju[2].l:=v[i,2].x; if intersect(ju[1],ju[2]) then continue; for j:=i+1 to n do begin insert(v[j-1,2],ju[2]);{将第 j-1 点放入矩形 2} ju[3].b:=v[j,2].y;ju[3].t:=v[j,2].y;{将第 j 至 n 点放入矩形 3} ju[3].r:=v[j,2].x;ju[3].l:=v[j,2].x; for ii:=j+1 to n do insert(v[ii,2],ju[3]); if intersect(ju[2],ju[3]) then continue; temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]); if temp<smin then smin:=temp; end; end; {flag=3 的情形} for j:=3 to n do begin for ii:=1 to n do v[ii,2]:=v[ii,0]; for ii:=1 to j-2 do for jj:=ii+1 to j-1 do if v[ii,2].y>v[jj,2].y then begin v0:=v[ii,2];v[ii,2]:=v[jj,2];v[jj,2]:=v0; end; ju[3].b:=v[j,2].y;ju[3].t:=v[j,2].y; ju[3].r:=v[j,2].x;ju[3].l:=v[j,2].x;
第 93 页 | 共 209 页

NOIP 2002 提高组 解题报告

for ii:=j+1 to n do insert(v[ii,2],ju[3]); for i:=2 to j-1 do begin ju[2].b:=v[i,2].y;ju[2].t:=v[i,2].y; ju[2].r:=v[i,2].x;ju[2].l:=v[i,2].x; for ii:=i+1 to j-1 do insert(v[ii,2],ju[2]); ju[1].b:=v[1,2].y;ju[1].t:=v[1,2].y; ju[1].r:=v[1,2].x;ju[1].l:=v[1,2].x; for ii:=2 to i-1 do insert(v[ii,2],ju[1]); if intersect(ju[1],ju[2]) or intersect(ju[2],ju[3]) or intersect(ju[1],ju[3]) then continue; temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]); if temp<smin then smin:=temp; end; end; {flag=4 的情形} for j:=3 to n do begin for ii:=1 to n do v[ii,2]:=v[ii,1]; for ii:=1 to j-2 do for jj:=ii+1 to j-1 do if v[ii,2].x>v[jj,2].x then begin v0:=v[ii,2];v[ii,2]:=v[jj,2];v[jj,2]:=v0; end; ju[3].b:=v[j,2].y;ju[3].t:=v[j,2].y; ju[3].r:=v[j,2].x;ju[3].l:=v[j,2].x; for ii:=j+1 to n do insert(v[ii,2],ju[3]); for i:=2 to j-1 do begin ju[2].b:=v[i,2].y;ju[2].t:=v[i,2].y; ju[2].r:=v[i,2].x;ju[2].l:=v[i,2].x; for ii:=i+1 to j-1 do insert(v[ii,2],ju[2]); ju[1].b:=v[1,2].y;ju[1].t:=v[1,2].y; ju[1].r:=v[1,2].x;ju[1].l:=v[1,2].x; for ii:=2 to i-1 do insert(v[ii,2],ju[1]); if intersect(ju[1],ju[2]) or intersect(ju[2],ju[3]) or intersect(ju[1],ju[3]) then continue; temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]); if temp<smin then smin:=temp; end; end; {flag=5 的情形} ju[1].b:=v[1,1].y;ju[1].t:=v[1,1].y; ju[1].r:=v[1,1].x;ju[1].l:=v[1,1].x; for i:=2 to n-1 do begin
第 94 页 | 共 209 页

NOIP 2002 提高组 解题报告

for ii:=1 to n do v[ii,2]:=v[ii,1]; for ii:=i to n-1 do for jj:=ii+1 to n do if v[ii,2].x>v[jj,2].x then begin v0:=v[ii,2];v[ii,2]:=v[jj,2];v[jj,2]:=v0; end; insert(v[i-1,2],ju[1]); ju[2].b:=v[i,2].y;ju[2].t:=v[i,2].y; ju[2].r:=v[i,2].x;ju[2].l:=v[i,2].x; if intersect(ju[1],ju[2]) then continue; for j:=i+1 to n do begin insert(v[j-1,2],ju[2]); ju[3].b:=v[j,2].y;ju[3].t:=v[j,2].y; ju[3].r:=v[j,2].x;ju[3].l:=v[j,2].x; for ii:=j+1 to n do insert(v[ii,2],ju[3]); if intersect(ju[2],ju[3]) then continue; temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]); if temp<smin then smin:=temp; end; end; end; end; end; begin{主程序} init; solve; writeln(smin); end. 点评:压轴题 据说,本次复赛主要是前三题的竞争,可见本题能得分的人相当 少,但是 K=1 应该说是送分的,K=2 也是比较容易的。通过测试,发现在 K=3 的 第 4、5 组测试数据中仅用到了 flag=1 的情形,也就是说,只要写出 flag=1 的 程序段就 OK 了(没写 flag=0,2,3,4,5 的同学偷着乐?) 注意:本人不能保证原作者提供的参考程序的准确及严密。

第 95 页 | 共 209 页

NOIP 2003 普及组 复赛试题

NOIP2003 普及组复赛试题
声明:试题来源?苏州 高斌

题一、乒乓球(Table.pas) 【问题背景】 国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革, 以推动 乒乓球运动在全球的普及。其中 11 分制改革引起了很大的争议,有一部分球员因为无法适 应新规则只能选择退役。华华就是其中一位,他退役之后走上了乒乓球研究工作,意图弄明 白 11 分制和 21 分制对选手的不同影响。 在开展他的研究之前, 他首先需要对他多年比赛的 统计数据进行一些分析,所以需要你的帮忙。 【问题描述】华华通过以下方式进行分析,首先将比赛每个球的胜负列成一张表,然后 分别计算在 11 分制和 21 分制下,双方的比赛结果(截至记录末尾) 。 比如现在有这么一份记录, (其中 W 表示华华获得一分,L 表示华华对手获得一分) : WWWWWWWWWWWWWWWWWWWWWWLW 在 11 分制下,此时比赛的结果是华华第一局 11 比 0 获胜,第二局 11 比 0 获胜,正在 进行第三局,当前比分 1 比 1。而在 21 分制下,此时比赛结果是华华第一局 21 比 0 获胜, 正在进行第二局,比分 2 比 1。如果一局比赛刚开始,则此时比分为 0 比 0。 你的程序就是要对于一系列比赛信息的输入(WL 形式) ,输出正确的结果。 【输入格式】每个输入文件包含若干行字符串(每行至多 20 个字母) ,字符串有大写的 W、L 和 E 组成。其中 E 表示比赛信息结束,程序应该忽略 E 之后的所有内容。 【输出格式】输出由两部分组成,每部分有若干行,每一行对应一局比赛的比分(按比 赛信息输入顺序) 。其中第一部分是 11 分制下的结果,第二部分是 21 分制下的结果,两部 分之间由一个空行分隔。 【输入样例】 WWWWWWWWWWWWWWWWWWWW WWLWE 【输出样例】 11:0 11:0 1:1 21:0 2:1

第 96 页 | 共 209 页

NOIP 2003 普及组 复赛试题

题二、数字游戏(Game.pas) 【问题描述】丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了 许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。 游戏是这样的, 在 你面前有一圈整数(一共 n 个) ,你要按顺序将其分为 m 个部分,各部分内的数字相加,相 加所得的 m 个结果对 10 取模后再相乘,最终得到一个数 k。游戏的要求是使你所得的 k 最 大或者最小。 例如,对于下面这圈数字(n=4,m=2) :

2 4 3
当要求最小值时, ((2-1) mod 10)×((4+3) mod 10)=1×7=7, 要求最大值时, 为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是,无论是负数还是正数,对 10 取模的 结果均为非负值。 丁丁请你编写程序帮他赢得这个游戏。 【输入格式】输入文件第一行有两个整数,n(1≤n≤50)和 m(1≤m≤9) 。以下 n 行 4 每行有个整数,其绝对值不大于 10 ,按顺序给出圈中的数字,首尾相接。 【输出格式】输出文件有两行,各包含一个非负整数。第一行是你程序得到的最小值, 第二行是最大值。 【输入样例】 4 2 4 3 -1 2 【输出样例】 7 81

-1

题三、栈(Stack.pas) 【问题背景】栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删 除操作的线性表。 栈有两种最重要的操作,即 pop(从栈顶弹出一个元素)和 push(将一个元素进栈) 。

第 97 页 | 共 209 页

NOIP 2003 普及组 复赛试题

栈的重要性不言自明, 任何一门数据结构的课程都会介绍栈。 宁宁同学在复习栈的基本 概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。 【问题描述】

1
输出序列 尾端 头端 头端

2

3

操作数序列

栈A

宁宁考虑的是这样一个问题:一个操作数序列,从 1,2,一直到 n(图示为 1 到 3 的情 况) ,栈 A 的深度大于 n。 现在可以进行两种操作, 1.将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的 push 操作) 2. 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的 pop 操作) 使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由 1 2 3 生成序列 2 3 1 的过程。 (原始状态如上图所示)
2 3 3 2 3

1 2 2 3

2 1 2 3 1

1

3 1

1

你的程序将对给定的 n,计算并输出由操作数序列 1,2,?,n 经过操作可能得到的输 出序列的总数。 【输入格式】 输入文件只含一个整数 n(1≤n≤18) 【输出格式】 输出文件只有一行,即可能输出序列的总数目 【输入样例】 3

第 98 页 | 共 209 页

NOIP 2003 普及组 复赛试题

【输出样例】 5 题四、麦森数(Mason.pas) P 【问题描述】形如 2 -1 的素数称为麦森数,这时 P 一定也是个素数。但反过来不一定, P 即如果 P 是个素数,2 -1 不一定也是素数。到 1998 年底,人们已找到了 37 个麦森数。最 大的一个是 P=3021377,它有 909526 位。麦森数有许多重要应用,它与完全数密切相关。 P 任务:从文件中输入 P(1000<P<3100000) ,计算 2 -1 的位数和最后 500 位数字(用十 进制高精度数表示) 【输入格式】 文件中只包含一个整数 P(1000<P<3100000) 【输出格式】 P 第一行:十进制高精度数 2 -1 的位数。 P 第 2-11 行:十进制高精度数 2 -1 的最后 500 位数字。 (每行输出 50 位,共输出 10 行, 不足 500 位时高位补 0) P 不必验证 2 -1 与 P 是否为素数。 【输入样例】 1279 【输出样例】 386 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000104079321946643990819252403273640855 38615262247266704805319112350403608059673360298012 23944173232418484242161395428100779138356624832346 49081399066056773207629241295093892203457731833496 61583550472959420547689811211693677147548478866962 50138443826029173234888531116082853841658502825560 46662248318909188018470682222031405210266984354887 32958028878050869736186900714720710555703168729087

第 99 页 | 共 209 页

NOIP 2003 提高组 复赛试题

第九届全国青少年信息学奥林匹克联赛(N0IP2003)
2003 年 11 月 29 日(农历二〇〇三年十一月初六) 提高组试题 三小时完成 声明:试题来源?苏州高斌

题一

神经网络

【问题背景】 人工神经网络(Artificial Neural Network)是一种新兴的具有自我学习能力的计算系统, 在模式识别、 函数逼近及贷款风险评估等诸多领域有广泛的应用。 对神经网络的研究一直是 当今的热门方向,兰兰同学在自学了一本神经网络的入门书籍后,提出了一个简化模型,他 希望你能帮助他用程序检验这个神经网络模型的实用性。 【问题描述】 在兰兰的模型中,神经网络就是一张有向图,图中的节点称为神经元,而且两个神经 元之间至多有一条边相连,下图是一个神经元的例子:

神经元〔编号为 1) 图中, X1—X3 是信息输入渠道, Y1-Y2 是信息输出渠道, C1 表示神经元目前的状态, Ui 是阈值,可视为神经元的一个内在参数。 神经元按一定的顺序排列,构成整个神经网络。在兰兰的模型之中,神经网络中的神 经无分为几层;称为输入层、输出层,和若干个中间层。每层神经元只向下一层的神经元 输出信息,只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。

兰兰规定,Ci 服从公式: (其中 n 是网络中所有神经元的数目)

Ci ?

( j,i )?E

?W C
ji

j

? Ui

第 100 页 | 共 209 页

NOIP 2003 提高组 复赛试题

公式中的 Wji(可能为负值)表示连接 j 号神经元和 i 号神经元的边的权值。当 Ci 大 于 0 时,该神经元处于兴奋状态,否则就处于平静状态。当神经元处于兴奋状态时,下一秒 它会向其他神经元传送信号,信号的强度为 Ci。 如此.在输入层神经元被激发之后,整个网络系统就在信息传输的推动下进行运作。 现在,给定一个神经网络,及当前输入层神经元的状态(Ci) ,要求你的程序运算出最后网 络输出层的状态。 【输入格式】 输入文件第一行是两个整数 n(1≤n≤20)和 p。接下来 n 行,每行两个整数,第 i+1 行是神经元 i 最初状态和其阈值(Ui) ,非输入层的神经元开始时状态必然为 0。再下面 P 行,每行由两个整数 i,j 及一个整数 Wij,表示连接神经元 i、j 的边权值为 Wij。 【输出格式】 输出文件包含若干行,每行有两个整数,分别对应一个神经元的编号,及其最后的状 态,两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态,并且按照编号由 小到大顺序输出! 若输出层的神经元最后状态均为 0,则输出 NULL。 【输入样例】 56 10 10 01 01 01 131 141 151 231 241 251 【输出样例】 31 41 51

题二

侦探推理

【问题描述】 明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中,于是他召集了一群同学 玩推理游戏。游戏的内容是这样的,明明的同学们先商量好由其中的一个人充当罪犯(在明

第 101 页 | 共 209 页

NOIP 2003 提高组 复赛试题

明不知情的情况下) ,明明的任务就是找出这个罪犯。接着,明明逐个询问每一个同学,被 询问者可能会说:

证词中出现的其他话,都不列入逻辑推理的内容。 明明所知道的是,他的同学中有 N 个人始终说假话,其余的人始终说真。 现在,明明需要你帮助他从他同学的话中推断出谁是真正的凶手,请记住,凶手只有一 个! 【输入格式】 输入由若干行组成,第一行有二个整数,M(1≤M≤20) 、N(1≤N≤M)和 P(1≤P≤100) ; M 是参加游戏的明明的同学数,N 是其中始终说谎的人数,P 是证言的总数。接下来 M 行, 每行是明明的一个同学的名字(英文字母组成,没有主格,全部大写) 。 往后有 P 行,每行开始是某个同学的名宇,紧跟着一个冒号和一个空格,后面是一句 证词,符合前表中所列格式。证词每行不会超过 250 个字符。 输入中不会出现连续的两个空格,而且每行开头和结尾也没有空格。 【输出格式】 如果你的程序能确定谁是罪犯,则输出他的名字;如果程序判断出不止一个人可能是 罪犯, 则输出 Cannot Determine; 如果程序判断出没有人可能成为罪犯, 则输出 Impossible。 【输入样例】 315 MIKE CHARLES KATE MIKE:I am guilty. MIKE:Today is Sunday. CHARLES:MIKE is guilty. KATE:I am guilty. KATE:How are you?? 【输出样例】 MIKE

题三
【问题描述】

加分二叉树

第 102 页 | 共 209 页

NOIP 2003 提高组 复赛试题

设一个 n 个节点的二叉树 tree 的中序遍历为(l,2,3,…,n) ,其中数字 1,2,3,…,n 为节点编 号。每个节点都有一个分数(均为正整数) ,记第 j 个节点的分数为 di,tree 及它的每个子 树都有一个加分,任一棵子树 subtree(也包含 tree 本身)的加分计算方法如下: subtree 的左子树的加分× subtree 的右子树的加分+subtree 的根的分数 若某个子树为主,规定其加分为 1,叶子的加分就是叶节点本身的分数。不考虑它的空 子树。 试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树 tree。要求输出; (1)tree 的最高加分 (2)tree 的前序遍历 【输入格式】 第 1 行:一个整数 n(n<30) ,为节点个数。 第 2 行:n 个用空格隔开的整数,为每个节点的分数(分数<100) 。 【输出格式】 第 1 行:一个整数,为最高加分(结果不会超过 4,000,000,000) 。 第 2 行:n 个用空格隔开的整数,为该树的前序遍历。 【输入样例】 5 5 7 1 2 10 【输出样例】 145 31245

题四

传染病控制

【问题背景】 近来,一种新的传染病肆虐全球。蓬莱国也发现了零星感染者,为防止该病在蓬莱国 大范围流行,该国政府决定不惜一切代价控制传染病的蔓延。不幸的是,由于人们尚未完 全认识这种传染病,难以准确判别病毒携带者,更没有研制出疫苗以保护易感人群。于是, 蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO(世界卫 生组织)以及全球各国科研部门的努力,这种新兴传染病的传播途径和控制方法已经研究 消楚,剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。 【问题描述】 研究表明,这种传染病的传播具有两种很特殊的性质; 第一是它的传播途径是树型的,一个人 X 只可能被某个特定的人 Y 感染,只要 Y 不 得病,或者是 XY 之间的传播途径被切断,则 X 就不会得病。 第二是,这种疾病的传播有周期性,在一个疾病传播周期之内,传染病将只会感染一 代患者,而不会再传播给下一代。 这些性质大大减轻了蓬莱国疾病防控的压力,并且他们已经得到了国内部分易感人群

第 103 页 | 共 209 页

NOIP 2003 提高组 复赛试题

的潜在传播途径图(一棵树) 。但是,麻烦还没有结束。由于蓬莱国疾控中心人手不够,同 时也缺乏强大的技术,以致他们在一个疾病传播周期内,只能设法切断一条传播途径,而 没有被控制的传播途径就会引起更多的易感人群被感染(也就是与当前已经被感染的人有 传播途径相连,且连接途径没有被切断的人群) 。当不可能有健康人被感染时,疾病就中止 传播。所以,蓬莱国疾控中心要制定出一个切断传播途径的顺序,以使尽量少的人被感染。 你的程序要针对给定的树,找出合适的切断顺序。 【输入格式】 输入格式的第一行是两个整数 n(1≤n≤300)和 p。接下来 p 行,每一行有两个整数 i 和 j,表示节点 i 和 j 间有边相连(意即,第 i 人和第 j 人之间有传播途径相连) 。其中节点 1 是已经被感染的患者。 【输出格式】 只有一行,输出总共被感染的人数。 【输入样例】 76 12 13 24 25 36 37 【输出样例】 3

第 104 页 | 共 209 页

NOIP 2004 普及组 复赛试题

第十届全国青少年信息学奥林匹克联赛复赛试题
来源?http://www.oifans.cn ( 普及组 三小时完成 ) 不高兴的津津 (unhappy.pas/dpr/c/cpp) 【问题描述】 津津上初中了。妈妈认为津津应该更加用功学习,所以津津除了上学之外,还要参加妈妈为 她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天 上课超过八个小时就会不高兴, 而且上得越久就会越不高兴。 假设津津不会因为其它事不高 兴,并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排,看看下周 她会不会不高兴;如果会的话,哪天最不高兴。 【输入文件】 输入文件 unhappy.in 包括七行数据,分别表示周一到周日的日程安排。每行包括两个小于 10 的非负整数,用空格隔开,分别表示津津在学校上课的时间和妈妈安排她上课的时间。 【输出文件】 输出文件 unhappy.out 包括一行,这一行只包含一个数字。如果不会不高兴则输出 0,如果 会则输出最不高兴的是周几(用 1, 2, 3, 4, 5, 6, 7 分别表示周一,周二,周三,周四,周五, 周六,周日) 。如果有两天或两天以上不高兴的程度相当,则输出时间最靠前的一天。 【样例输入】 53 62 72 53 54 04 06 【样例输出】

第 105 页 | 共 209 页

NOIP 2004 普及组 复赛试题

3 花生采摘 (peanuts.pas/dpr/c/cpp) 【问题描述】 鲁宾逊先生有一只宠物猴,名叫多多。这天,他们两个正沿着乡间小路散步,突然发现路边 的告示牌上贴着一张小小的纸条: “欢迎免费品尝我种的花生!——熊字” 。 鲁宾逊先生和多多都很开心,因为花生正是他们的最爱。在告示牌背后,路边真的有一块花 生田,花生植株整齐地排列成矩形网格(如图 1) 。有经验的多多一眼就能看出,每棵花生 植株下的花生有多少。为了训练多多的算术,鲁宾逊先生说: “你先找出花生最多的植株, 去采摘它的花生;然后再找出剩下的植株里花生最多的,去采摘它的花生;依此类推,不过 你一定要在我限定的时间内回到路边。 ”

我们假定多多在每个单位时间内,可以做下列四件事情中的一件: 1) 2) 3) 4) 从路边跳到最靠近路边(即第一行)的某棵花生植株; 从一棵植株跳到前后左右与之相邻的另一棵植株; 采摘一棵植株下的花生; 从最靠近路边(即第一行)的某棵花生植株跳回路边。

现在给定一块花生田的大小和花生的分布, 请问在限定时间内, 多多最多可以采到多少个花 生?注意可能只有部分植株下面长有花生,假设这些植株下的花生个数各不相同。 例如在图 2 所示的花生田里,只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生,个数分 别为 13, 7, 15, 9。沿着图示的路线,多多在 21 个单位时间内,最多可以采到 37 个花生。 【输入文件】 输入文件 peanuts.in 的第一行包括三个整数,M, N 和 K,用空格隔开;表示花生田的大小为 M * N(1 <= M, N <= 20) ,多多采花生的限定时间为 K(0 <= K <= 1000)个单位时间。接 下来的 M 行, 每行包括 N 个非负整数, 也用空格隔开; 第 i + 1 行的第 j 个整数 Pij (0 <= Pij <= 500)表示花生田里植株(i, j)下花生的数目,0 表示该植株下没有花生。 【输出文件】 输出文件 peanuts.out 包括一行,这一行只包含一个整数,即在限定时间内,多多最多可以

第 106 页 | 共 209 页

NOIP 2004 普及组 复赛试题

采到花生的个数。 【样例输入 1】 6 7 21 0000000 0 0 0 0 13 0 0 0000007 0 15 0 0 0 0 0 0009000 0000000 【样例输出 1】 37 【样例输入 2】 6 7 20 0000000 0 0 0 0 13 0 0 0000007 0 15 0 0 0 0 0 0009000 0000000 【样例输出 2】 28

第 107 页 | 共 209 页

NOIP 2004 普及组 复赛试题

FBI 树 (fbi.pas/dpr/c/cpp) 【问题描述】 我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为 B 串,全“1”串称为 I 串,既含“0”又含“1”的串则称为 F 串。 FBI 树是一种二叉树[1],它的结点类型也包括 F 结点,B 结点和 I 结点三种。由一个长度为 2N 的“01”串 S 可以构造出一棵 FBI 树 T,递归的构造方法如下: 1) T 的根结点为 R,其类型与串 S 的类型相同;

2) 若串 S 的长度大于 1,将串 S 从中间分开,分为等长的左右子串 S1 和 S2;由左子 串 S1 构造 R 的左子树 T1,由右子串 S2 构造 R 的右子树 T2。 现在给定一个长度为 2N 的“01”串,请用上述构造方法构造出一棵 FBI 树,并输出它的后 序遍历[2]序列。 【输入文件】 输入文件 fbi.in 的第一行是一个整数 N(0 <= N <= 10) ,第二行是一个长度为 2N 的“01” 串。 【输出文件】 输出文件 fbi.out 包括一行,这一行只包含一个字符串,即 FBI 树的后序遍历序列。 【样例输入】 3 10001011 【样例输出】 IBFBBBFIBFIIIFF 【数据规模】 对于 40%的数据,N <= 2; 对于全部的数据,N <= 10。

第 108 页 | 共 209 页

NOIP 2004 普及组 复赛试题

火星人 (martian.pas/dpr/c/cpp) 【问题描述】 人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语 言,但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的,首先,火星 人把一个非常大的数字告诉人类科学家, 科学家破解这个数字的含义后, 再把一个很小的数 字加到这个大数上面,把结果告诉火星人,作为人类的回答。 火星人用一种非常简单的方式来表示数字——掰手指。 火星人只有一只手, 但这只手上有成 千上万的手指,这些手指排成一列,分别编号为 1,2,3??。火星人的任意两根手指都能 随意交换位置,他们就是通过这方法计数的。 一个火星人用一个人类的手演示了如何用手指计数。 如果把五根手指——拇指、 食指、 中指、 无名指和小指分别编号为 1, 2, 3, 4 和 5, 当它们按正常顺序排列时, 形成了 5 位数 12345, 当你交换无名指和小指的位置时, 会形成 5 位数 12354, 当你把五个手指的顺序完全颠倒时, 会形成 54321,在所有能够形成的 120 个 5 位数中,12345 最小,它表示 1;12354 第二小, 它表示 2;54321 最大,它表示 120。下表展示了只有 3 根手指时能够形成的 6 个 3 位数和 它们代表的数字: 三进制数 123 132 213 231 312 321 代表的数字 1 2 3 4 5 6

现在你有幸成为了第一个和火星人交流的地球人。 一个火星人会让你看他的手指, 科学家会 告诉你要加上去的很小的数。 你的任务是, 把火星人用手指表示的数与科学家告诉你的数相 加, 并根据相加的结果改变火星人手指的排列顺序。 输入数据保证这个结果不会超出火星人 手指能表示的范围。 【输入文件】

第 109 页 | 共 209 页

NOIP 2004 普及组 复赛试题

输入文件 martian.in 包括三行,第一行有一个正整数 N,表示火星人手指的数目(1 <= N <= 10000) 。第二行是一个正整数 M,表示要加上去的小整数(1 <= M <= 100) 。下一行是 1 到 N 这 N 个整数的一个排列,用空格隔开,表示火星人手指的排列顺序。 【输出文件】 输出文件 martian.out 只有一行,这一行含有 N 个整数,表示改变后的火星人手指的排列顺 序。每两个相邻的数中间用一个空格分开,不能有多余的空格。 【样例输入】 5 3 12345 【样例输出】 12453 【数据规模】 对于 30%的数据,N<=15; 对于 60%的数据,N<=50; 对于全部的数据,N<=10000; -------------------------------------------------------------------------------[1] 二叉树:二叉树是结点的有限集合,这个集合或为空集,或由一个根结点和两棵不相交 的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。 [2] 后序遍历:后序遍历是深度优先遍历二叉树的一种方法,它的递归定义是:先后序遍历 左子树,再后序遍历右子树,最后访问根。

第 110 页 | 共 209 页

NOIP 2004 普及组 解题参考

NOIP 普及组复赛参考程序 NOIP2004 普及组解题参考
第一题:不高兴的津津 方法:枚举 程序: program unhappy; {writen by lxq 2004.11.20} var a,i,x,y,d,max : byte; begin assign(input,'unhappy.in'); reset(input); assign(output,'unhappy.out'); rewrite(output); d := 0; max :=8; for i := 1 to 7 do begin readln(x,y); a := x+y; if a>max then begin max :=a; d := i; end; end; writeln(d); close(input); close(output); end. 第二题:花生采摘 方法:排个序,然后迭代递推 程序: program peanuts; {writen by lxq 2004.11.20} type mytype=record x,y,d:integer; end; var time,all,num,i,j,m,n,k,u,v,z:integer; q:array[1..400] of mytype; t:mytype; begin all:=0; assign(input,'peanuts.in'); reset(input); readln(m,n,k); for i:=1 to m do begin for j:=1 to n do

第 111 页 | 共 209 页

NOIP 2004 普及组 解题参考

begin read(u); if u>0 then begin inc(all); q[all].x:=i;q[all].y:=j;q[all].d:=u; if all>1 then begin v:=1; while q[v].d>u do inc(v); t:=q[all]; for z:=all downto v+1 do q[z]:=q[z-1]; q[v]:=t; end; end; end; readln; end; close(input); num:=0;time:=0;u:=0;v:=q[1].y; for i:=1 to all do begin if time+abs(q[ i ].x-u)+abs(q[ i ].y-v)+1+q[ i ].x<=k then begin inc(num,q[ i ].d); time:=time+abs(q[ i ].x-u)+abs(q[ i ].y-v)+1; u:=q[ i ].x;v:=q[ i ].y; end else break; end; assign(output,'peanuts.out'); rewrite(output); writeln(num); close(output); end. 第三题 FBI 树 方法:递归即可,按后序遍历直接边生成边打印。 程序: program fbi; {writen by lxq 2004.11.20} var f:array[1..1024] of char; i,k,n:integer; c:char; function lastorder(i,j,n:integer):char;

第 112 页 | 共 209 页

NOIP 2004 普及组 解题参考

var lc,rc:char; begin if n=0 then lastorder:=f[ i ] else begin lc:=lastorder(i,(i+j) div 2,n-1); write(lc); rc:=lastorder((i+j) div 2+1,j,n-1); write(rc); if lc=rc then lastorder:=lc else lastorder:='F'; end; end; begin assign(input,'fbi.in'); reset(input); readln(n); k:=1; for i:=1 to n do k:=k*2; for i:=1 to k do begin read(c); if c='0' then f[ i ]:='B' else f[ i ]:='I' end; readln; close(input); assign(output,'fbi.out'); rewrite(output); writeln(lastorder(1,k,n)); close(output); end. 第四题 火星人 方法:排列生成法,直接从指定序列用排列产生方法顺序生成到后面 M 个。 程序: program martian; {writen by lxq 2004.11.20} const maxn=10000; var a:array[1..maxn+1] of integer; b:array[1..maxn+1] of boolean; n,m,i,p,k:integer; begin assign(input,'martian.in'); reset(input); readln(n); readln(m); fillchar(b,sizeof(b),false);

第 113 页 | 共 209 页

NOIP 2004 普及组 解题参考

for i:=1 to n do begin read(a[ i ]);b[a[ i >:=true end;p:=n+1; k:=-1; while true do begin if p>n then begin dec(p); inc(k); b[a[ i >:=false; if k=m then break; end; repeat inc(a[ i ] ); until not b[a[ i ] ]; b[a[ i ] ]:=true; if a[ i ] >n then begin b[a[ i ] ]:=false;dec(p);b[a[ i >:=false end else begin inc(p); a[ i ] :=0 end; end; assign(output,'martian.out'); rewrite(output); for i:=1 to n-1 do write(a[ i ],' ');writeln(a[n]); close(output) end. 本人提示:题目火星人可用 C++STL 库函数:next_permutation()解决,十分简单。

第 114 页 | 共 209 页

NOIP 2004 提高组 复赛试题

第十届全国青少年信息学奥林匹克联赛复赛试题 (提高组 3 小时完成) 试题来源?http://www.oifans.cn 一、津津的储蓄计划 (Save.pas/dpr/c/cpp). 【问题描述】 津津的零花钱一直都是自己管理。 每个月的月初妈妈给津津 300 元钱, 津津 会预算这个月的花销,并且总能做到实际花销和预算的相同。 为了让津津学习如何储蓄, 妈妈提出, 津津可以随时把整百的钱存在她那里, 到了年末她会加上 20%还给津津。因此津津制定了一个储蓄计划:每个月的月 初,在得到妈妈给的零花钱后,如果她预计到这个月的月末手中还会有多于 100 元或恰好 100 元,她就会把整百的钱存在妈妈那里,剩余的钱留在自己手中。 例如 11 月初津津手中还有 83 元,妈妈给了津津 300 元。津津预计 11 月的 花销是 180 元,那么她就会在妈妈那里存 200 元,自己留下 183 元。到了 11 月 月末,津津手中会剩下 3 元钱。 津津发现这个储蓄计划的主要风险是, 存在妈妈那里的钱在年末之前不能取 出。有可能在某个月的月初,津津手中的钱加上这个月妈妈给的钱,不够这个月 的原定预算。如果出现这种情况,津津将不得不在这个月省吃俭用,压缩预算。 现在请你根据 2004 年 1 月到 12 月每个月津津的预算, 判断会不会出现这种 情况。如果不会,计算到 2004 年年末,妈妈将津津平常存的钱加上 20%还给津 津之后,津津手中会有多少钱。 【输入文件】 输入文件 save.in 包括 12 行数据,每行包含一个小于 350 的非负整数,分 别表示 1 月到 12 月津津的预算。 【输出文件】 输出文件 save.out 包括一行,这一行只包含一个整数。如果储蓄计划实施 过程中出现某个月钱不够用的情况,输出-X,X 表示出现这种情况的第一个月; 否则输出到 2004 年年末津津手中会有多少钱。 【样例输入 1】
第 115 页 | 共 209 页

NOIP 2004 提高组 复赛试题

290 230 280 200 300 170 340 50 90 80 200 60 【样例输出 1】 -7 【样例输入 2】 290 230 280 200 300 170 330 50 90 80 200 60 【样例输出 2】 1580

二、合并果子 (fruit.pas/dpr/c/cpp) 【问题描述】 在一个果园里, 多多已经将所有的果子打了下来, 而且按果子的不同种类分 成了不同的堆。多多决定把所有的果子合成一堆。

第 116 页 | 共 209 页

NOIP 2004 提高组 复赛试题

每一次合并, 多多可以把两堆果子合并到一起, 消耗的体力等于两堆果子的 重量之和。可以看出,所有的果子经过 n-1 次合并之后,就只剩下一堆了。多多 在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家, 所以多多在合并果子时要尽可能地节 省体力。假定每个果子重量都为 1,并且已知果子的种类数和每种果子的数目, 你的任务是设计出合并的次序方案, 使多多耗费的体力最少, 并输出这个最小的 体力耗费值。 例如有 3 种果子,数目依次为 1,2,9。可以先将 1、2 堆合并,新堆数目 为 3,耗费体力为 3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目 为 12,耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明 15 为最小的 体力耗费值。 【输入文件】 输入文件 fruit.in 包括两行,第一行是一个整数 n(1<=n<=10000),表示 果子的种类数。 第二行包含 n 个整数, 用空格分隔, 第 i 个整数 ai(1<=ai<=20000) 是第 i 种果子的数目。 【输出文件】 输出文件 fruit.out 包括一行, 这一行只包含一个整数, 也就是最小的体力 耗费值。输入数据保证这个值小于 231。 【样例输入】 3 1 2 9 【样例输出】 15 【数据规模】

对于 30%的数据,保证有 n<=1000: 对于 50%的数据,保证有 n<=5000; 对于全部的数据,保证有 n<=10000。 三、合唱队形

第 117 页 | 共 209 页

NOIP 2004 提高组 复赛试题

(chorus.pas/dpr/c/cpp) 【问题描述】 N 位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的 K 位同学排成合唱队形。 合唱队形是指这样的一种队形: 设 K 位同学从左到右依次编号为 1, 2?, K, 他 们 的 身 高 分 别 为 T1 , T2 , ? , TK , 则他们的身高满足 T1<...<Ti>Ti+1>?>TK(1<=i<=K)。 你的任务是,已知所有 N 位同学的身高,计算最少需要几位同学出列,可以 使得剩下的同学排成合唱队形。 【输入文件】 输入文件 chorus.in 的第一行是一个整数 N(2<=N<=100),表示同学的总数。 第一行有 n 个整数,用空格分隔,第 i 个整数 Ti(130<=Ti<=230)是第 i 位同学 的身高(厘米)。 【输出文件】 输出文件 chorus.out 包括一行,这一行只包含一个整数,就是最少需要几 位同学出列。 【样例输入】 8 186 186 150 200 160 130 197 220 【样例输出】 4 【数据规模】 对于 50%的数据,保证有 n<=20; 对于全部的数据,保证有 n<=100。

四、虫食算 (alpha.pas/dpr/c/cpp)
第 118 页 | 共 209 页

NOIP 2004 提高组 复赛试题

【问题描述】 所谓虫食算, 就是原先的算式中有一部分被虫子啃掉了, 需要我们根据剩下 的数字来判定被啃掉的字母。来看一个简单的例子: 43#9865#045 8468#6633 44445506978

+

其中#号代表被虫子啃掉的数字。根据算式,我们很容易判断:第一行的两 个数字分别是 5 和 3,第二行的数字是 5。 现在,我们对问题做两个限制: 首先,我们只考虑加法的虫食算。这里的加法是 N 进制加法,算式中三个数 都有 N 位,允许有前导的 0。 其次,虫子把所有的数都啃光了,我们只知道哪些数字是相同的,我们将相 同的数字用相同的字母表示,不同的数字用不同的字母表示。如果这个算式是 N 进制的,我们就取英文字母表午的前 N 个大写字母来表示这个算式中的 0 到 N-1 这 N 个不同的数字:但是这 N 个字母并不一定顺序地代表 0 到 N-1)。输入数据 保证 N 个字母分别至少出现一次。

+

BADC CRDA DCCC

上面的算式是一个 4 进制的算式。 很显然, 我们只要让 ABCD 分别代表 0123, 便可以让这个式子成立了。你的任务是,对于给定的 N 进制加法算式,求出 N 个不同的字母分别代表的数字, 使得该加法算式成立。 输入数据保证有且仅有一 组解, 【输入文件】 输入文件 alpha.in 包含 4 行。第一行有一个正整数 N(N<=26),后面的 3 行 每行有一个由大写字母组成的字符串, 分别代表两个加数以及和。 这 3 个字符串 左右两端都没有空格,从高位到低位,并且恰好有 N 位。 【输出文件】 输出文件 alpha.out 包含一行。在这一行中,应当包含唯一的那组解。解是
第 119 页 | 共 209 页

NOIP 2004 提高组 复赛试题

这样表示的:输出 N 个数字,分别表示 A,B,C??所代表的数字,相邻的两个 数字用一个空格隔开,不能有多余的空格。 【样例输入】 5 ABCED BDACE EBBAA 【样例输出】 1 0 3 4 2 【数据规模】 对于 30%的数据,保证有 N<=10; 对于 50%的数据,保证有 N<=15; 对于全部的数据,保证有 N<=26。

第 120 页 | 共 209 页

NOIP 2004 提高组 解题报告

NOIP2004 提高组复赛 解题报告
本人未经原作者允许即引用,并非用于商业用途,在这里表示歉意 二次引用请注明出处~,切勿用于盈利或其它~
津津的储蓄计划 解题报告 <问题描述> 津津的零花钱一直都是自己管理。每个月的月初妈妈给津津 300 元钱,津津会预算这 个月的花销,并且总能做到实际花销和预算的相同。 为了让津津学习如何储蓄,妈妈提出,津津可以随时把整百的钱存在她那里,到了年 末她会加上 20%还给津津。因此津津制定了一个储蓄计划:每个月的月初,在得到妈妈给 的零花钱后,如果她预计到这个月的月末手中还会有多于 100 元或恰好 100 元,她就会把 整百的钱存在妈妈那里,剩余的钱留在自己手中。 例如 11 月初津津手中还有 83 元,妈妈给了津津 300 元。津津预计 11 月的花销是 180 元,那么她就会在妈妈那里存 200 元,自己留下 183 元。到了 11 月月末,津津手中 会剩下 3 元钱。 津津发现这个储蓄计划的主要风险是,存在妈妈那里的钱在年末之前不能取出。有可 能在某个月的月初,津津手中的钱加上这个月妈妈给的钱,不够这个月的原定预算。如果出 现这种情况,津津将不得不在这个月省吃俭用,压缩预算。 现在请你根据 2004 年 1 月到 12 月每个月津津的预算,判断会不会出现这种情况。 如果不会,计算到 2004 年年末,妈妈将津津平常存的钱加上 20%还给津津之后,津津手 中会有多少钱。 - 输入文件 输入文件 save.in 包括 12 行数据, 每行包含一个小于 350 的非负整数, 分别表示 1 月到 12 月津津的预算。 - 输出文件 输出文件 save.out 包括一行,这一行只包含一个整数。如果储蓄计划实施过程中出 现某个月钱不够用的情况,输出-X,X 表示出现这种情况的第一个月;否则输出到 2004 年年末津津手中会有多少钱。 - 样例输入 1 290/230/280/200/300/170/340/50/90/80/200/60 - 样例输出 1 -7 - 样例输入 2 290/230/280/200/300/170/330/50/90/80/200/60 - 样例输出 2 1580 <算法分析> 这是本次分区联赛当中最简单的题,算法也很简单:模拟法。 每个月把津津手上的钱加上妈妈给的300元,再减去预算,得到当前手中的钱,假如这 个钱的值是负数(出现亏损),那么就输出负的月数,接着算出存入的钱,并且将手中的钱

第 121 页 | 共 209 页

NOIP 2004 提高组 解题报告

减去。如此往复,直到最后按要求输出结果或者中间已经停止。 <数据结构> 边读边处理。 只需要记录当钱手中的钱和已存入的钱即可。 时间、 空间复杂度均为常数。 <代码清单> #include <fstream> using namespace std; ifstream fin("save.in"); ofstream fout("save.out"); void init() { int p, save = 0, cnt = 0; for (int i = 1; i <= 12; i ++) { fin >> p; cnt = cnt + 300 - p; while (cnt >= 100) { save += 100; cnt -= 100; } if (cnt < 0) { fout << - i << endl; return; } } fout << cnt + int(save * 1.2) << endl; } int main() { init(); return 0; } <小结> 这是本次 NOIP 最简单、 最基本的问题。 选手只要读清题目, 然后动手做就可以了。 解决此类问题没有什么技巧,最重要的是不在关键时刻出现低级错误。 合并果子 解题报告 <问题描述> 在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同 的堆。多多决定把所有的果子合成一堆。

第 122 页 | 共 209 页

NOIP 2004 提高组 解题报告

每一次合并, 多多可以把两堆果子合并到一起, 消耗的体力等于两堆果子的重量之和。 可以看出,所有的果子经过 n-1 次合并之后,就只剩下一堆了。多多在合并果子时总共消 耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。 假定每个果子重量都为 1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合 并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。 例如有 3 种果子,数目依次为 1,2,9。可以先将 1、2 堆合并,新堆数目为 3,耗 费体力为 3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 12,耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明 15 为最小的体力耗费值。 - 输入文件 输入文件 fruit.in 包括两行,第一行是一个整数 n(1<=n<=10000),表示果子的 种类数。第二行包含 n 个整数,用空格分隔,第 i 个整数 ai(1<=ai<=20000)是第 i 种 果子的数目。 - 输出文件 输出文件 fruit.out 包括一行,这一行只包含一个整数,也就是最小的体力耗费值。 输入数据保证这个值小于 231。 - 样例输入 3 1 2 9 - 样例输出 15 - 数据规模 对于30%的数据,保证有n<=1000: 对于50%的数据,保证有n<=5000; 对于全部的数据,保证有n<=10000。 <算法分析> 将这个问题换一个角度描述:给定n个叶结点,每个结点有一个权值W[i],将它们中 两个、两个合并为树,假设每个结点从根到它的距离是D[i],使得最终∑(wi + di)最小。 于是,这个问题就变为了经典的Huffman树问题。Huffman树的构造方法如下: (1) 从森林里取两个权和最小的结点 (2) 将它们的权和相加,得到新的结点,并且把原结点删除,将新结点插入到森林 中 (3) 重复(1),直到整个森林里只有一棵树。 这个方法的正确性可以参见数据结构。 <数据结构> 很显然,问题当中需要执行的操作是:(1) 从一个表中取出最小的数 (2) 插入一个 数字到这个表中。 支持动态Extract_Min和Insert操作的数据结构,我们可以选择用堆来实现。堆是 一种完全二叉树,且保证根结点的值严格大于(或小于)其子孙结点。具体实现方法可以参 见数据结构。 于是整体算法的时间复杂度为O(nlogn),空间复杂度为O(n)。

第 123 页 | 共 209 页

NOIP 2004 提高组 解题报告

但是,有没有更好的方法呢?很显然,每次合并两个结点以后,得到的大小是严格递增 的,于是我们可以维护两个表,一个是原数字A,一个是新加入的数字B。这样,每次就一 定是在A和B的头部取数,在A和B的尾部删除。这样,时间复杂度就降到了O(n)。因为a[i] <= 20000,所以排序也可以用o(20000)的方法来实现,整体时间复杂度为O(n)。(感 谢BCBill提供这个方法) <代码清单> #include <fstream> #include <list> #include <algorithm> using namespace std; ifstream fin("fruit.in"); ofstream fout("fruit.out"); int n; list <int> a, b; void init() { int p; fin >> n; for (int i = 0; i < n; i ++) { fin >> p; a.push_back(p); } a.sort(); } int get() { int ans; if (a.empty()) { ans = b.front(); b.pop_front(); return ans; } if (b.empty()) { ans = a.front(); a.pop_front(); return ans; } if (a.front() < b.front()) { ans = a.front(); a.pop_front(); return ans; } else { ans = b.front(); b.pop_front(); return ans; }

第 124 页 | 共 209 页

NOIP 2004 提高组 解题报告

} void work() { int p, sum = 0; for (int i = 0; i < n - 1; i ++) { p = get() + get(); b.push_back(p); sum += p; } fout << sum << endl; } int main() { init(); work(); return 0; } <小结> 读清问题的描述是很重要的! 很多选手都将这个问题看成了最小代价子母树。 审清 题目是解决问题的首要条件。当然,灵活地使用数据结构也是解决问题的关键。简单的线性 表在这里充分地发挥了它的优势,使程序的效率得到了很大的提高 合唱队形 解题报告 <问题描述> N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成 合唱队形。 合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身 高分别为T1,T2,…,TK, 则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。 你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下 的同学排成合唱队形。 - 输入文件 输入文件chorus.in的第一行是一个整数N(2<=N<=100),表示同学的总数。第一 行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。 - 输出文件 输出文件chorus.out包括一行,这一行只包含一个整数,就是最少需要几位同学出 列。 - 样例输入 8 186 186 150 200 160 130 197 220 - 样例输出 4 - 数据规模 对于50%的数据,保证有n<=20;

第 125 页 | 共 209 页

NOIP 2004 提高组 解题报告

对于全部的数据,保证有n<=100。 <算法分析> 动态规划。最基本的想法是:枚举中间最高的一个人,接着对它的左边求最长上升序列 (注意序列中最高的同学不应高过基准),对右边求最长下降序列(同样的,序列中最高的 同学不应高过基准)。时间复杂度为O(n^3),算法实现起来也很简单。 接着对这个算法进行分析,我们不难发现,假如还是基于枚举一个同学的话,设 Incsq[i]表示了1 - i的最长上升序列,Decsq[i]表示了i - n的最长下降序列,那么, Current[i] = Incsq[i] + Decsq[i] - 1(两个数组中i被重复计算了) 那么,我们只需要先求好最长上升和下降序列,然后枚举中间最高的同学就可以了。 <算法优化> 求最长上升序列的经典状态转移方程为: opt[i] = max{opt[j]+1, 其中 i<j<=n, 且 list[j]>list[i]} 我们对状态转移方程稍微做一些修改: opt[i] = max{opt[i+1], min{j, rec[j]>=list[i]}} rec[j] = list[i] 很明显可以看出,在 opt[i]的寻找 j 的过程当中,查询序列是单调的,于是可以用二 分法,就十分巧妙地在 logn 的时间内找到指定的 j,而问题的总体复杂度为 O(nlogn)。 这样,这个问题的算法效率就得到了大幅度的提升,即便 n 是 106,也可以轻松应对。 <代码清单> #include <fstream> #include <cstring> using namespace std; ifstream fin("chorus.in"); ofstream fout("chorus.out"); const int maxn = 100; int n, a[maxn]; int incsq[maxn], decsq[maxn]; void init() { fin >> n; for (int i = 0; i < n; i ++) fin >> a[i]; } void LIncSeq() { int i, low, high, mid, ans = 0; int sol[maxn];

第 126 页 | 共 209 页

NOIP 2004 提高组 解题报告

for (i = 0; i < n; i ++) { low = 1; high = ans; while (low <= high) { mid = (low + high) >> 1; if (sol[mid] < a[i]) low = mid + 1; else high = mid - 1; } if (low > ans) ans ++; sol[low] = a[i]; incsq[i] = ans; } } void LDecSeq() { int i, low, high, mid, ans = 0; int sol[maxn]; for (i = 0; i < n; i ++) { low = 1; high = ans; while (low <= high) { mid = (low + high) >> 1; if (sol[mid] > a[i]) low = mid + 1; else high = mid - 1; } if (low > ans) ans ++; sol[low] = a[i]; decsq[i] = ans; } } void work() { int i, max = 0; LIncSeq(); LDecSeq(); for (i = 0; i < n; i ++) if (incsq[i] + decsq[i] - 1 > max) max = incsq[i] + decsq[i] - 1; fout << n - max << endl; }

第 127 页 | 共 209 页

NOIP 2004 提高组 解题报告

int main() { init(); work(); return 0; } <小结> 问题虽然简单,仍然不能放过思考的余地。O(n^3)的算法是可以通过所有测试数 据的,但是 nlogn 的算法里,不但体现了二分法的思想,而且也体现了多次动态规划的思 想,这个思想在解决很多问题的时候,都有很大的作用

虫食算 解题报告 <问题描述> 所谓虫食算, 就是原先的算式中有一部分被虫子啃掉了, 需要我们根据剩下的数字来判 定被啃掉的字母。来看一个简单的例子: 43#9865#045 + 8468#6633 其中#号代表被虫子啃掉的数字。根据算式,我们很容易判断:第一行的两个数字分 别是 5 和 3,第二行的数字是 5。 现在,我们对问题做两个限制: 首先, 我们只考虑加法的虫食算。 这里的加法是 N 进制加法, 算式中三个数都有 N 位, 允许有前导的 0。 其次,虫子把所有的数都啃光了,我们只知道哪些数字是相同的,我们将相同的数字 用相同的字母表示,不同的数字用不同的字母表示。如果这个算式是 N 进制的,我们就取 英文字母表午的前 N 个大写字母来表示这个算式中的 0 到 N-1 这 N 个不同的数字:但是这 N 个字母并不一定顺序地代表 0 到 N-1)。输入数据保证 N 个字母分别至少出现一次。 BADC + CRDA DCCC 上面的算式是一个 4 进制的算式。很显然,我们只要让 ABCD 分别代表 0123,便可 以让这个式子成立了。你的任务是,对于给定的 N 进制加法算式,求出 N 个不同的字母分 别代表的数字,使得该加法算式成立。输入数据保证有且仅有一组解, - 输入文件 输入文件 alpha.in 包含 4 行。 第一行有一个正整数 N(N<=26), 后面的 3 行每行有 一个由大写字母组成的字符串,分别代表两个加数以及和。这 3 个字符串左右两端都没有 空格,从高位到低位,并且恰好有 N 位。 - 输出文件 输出文件 alpha.out 包含一行。在这一行中,应当包含唯一的那组解。解是这样表 示的:输出 N 个数字,分别表示 A,B,C……所代表的数字,相邻的两个数字用一个空格隔 开,不能有多余的空格。 - 样例输入 5

第 128 页 | 共 209 页

NOIP 2004 提高组 解题报告

ABCED BDACE EBBAA - 样例输出 1 0 3 4 2 - 数据规模 对于 30%的数据,保证有 N<=10; 对于 50%的数据,保证有 N<=15; 对于全部的数据,保证有 N<=26。 <算法分析> 经典的搜索题。最单纯的搜索的时间复杂度为 O(n!),是会非常严重的超时的。计算 机是很“笨”的,它不会思考,在盲目搜索的过程中,很容易出现这种情况: 计算机在某一位搜索出了一个算式 1 + 1 = 3,并且继续搜索。 明显, 人眼很容易就看出这是不合法的, 但计算机不会。 于是, 我们想到了第一个剪枝: 每次搜索的时候,从最后向前判断是否有不合法的式子。 这一个剪枝非常简单,但是效果却非常的好。因为它剪去了很多不必要的搜索。为了配 合这一种剪枝更好的实行,搜索顺序的改变也成为大大提高程序效率的关键:从右往左,按 照字母出现顺序搜索, 有很大程度上提高了先剪掉废枝的情况, 使程序的效率得到大大的提 高。 有了以上两个剪枝, 程序就已经可以通过大部分测试点了。 但是有没有更多的剪枝呢? 答案是肯定的。 根据前面的剪枝,我们可以找到类似的几个剪枝: 对于 a + b = c 的形式,假如: A***?*** + B*?**?** C***???* 其中*代表已知,?代表未知。那么,A + B 与 C 的情况并不能直接确定。但是,假如 (A + B) % N 与(A + B + 1) % N 都不等于 C 的话,那么这个等式一定是不合法的。 因为它只有进位和不进位的两种情况。 同样,我们在一个数组里记录了 Used[i]表示一个数字有没有用过,那么,对于某一 位 A + B = C 的等式,如果已经得到了两个数,另一个数还待搜索的时候,我们还可以根 据这个加入一个剪枝: 例如 A + ? = C 的形式, 考虑不进位的情况,则?处为 P1 = (C - A + N) % N 假如考虑进位的情况,则?处为 P2 = (C - A - 1 + N) % N 假如 P1、P2 均被使用过,那么这个搜索一定是无效的,可以剪去。 有了以上的剪枝,就可以很轻松地通过所有的测试数据了。当然,还有很多值得思考的 剪枝以及其他的思路,例如枚举进位、解方程(但是可能需要枚举)等,在这里就不详细讨 论了。 <代码清单> #include <fstream>

第 129 页 | 共 209 页

NOIP 2004 提高组 解题报告

#include <string> using namespace std; ifstream fin("alpha.in"); ofstream fout("alpha.out"); bool finish, hash[256], used[27]; int n, stk[27]; string a, b, c; string word; void init() { fin >> n >> a >> b >> c; finish = false; } void outsol() { int i, ans[27]; for (i = 0; i < n; i ++) ans[word[i] - 65] = stk[i]; fout << ans[0]; for (i = 1; i < n; i ++) fout << " " << ans[i]; fout << endl; finish = true; } void addup(char ch) { if (!hash[ch]) { hash[ch] = true; word = word + ch; } } string change(string str, char x, char y) { for (int i = 0; i < n; i ++) if (str[i] == x) str[i] = y; return str; } void pre_doing() {

第 130 页 | 共 209 页

NOIP 2004 提高组 解题报告

word = ""; memset(hash, 0, sizeof(hash)); for (int i = n - 1; i >= 0; i --) { addup(a[i]); addup(b[i]); addup(c[i]); } memset(used, 0, sizeof(used)); } bool bad() { int p, g = 0; for (int i = n - 1; i >= 0; i --) { if (a[i] >= n || b[i] >= n || c[i] >= n) return false; p = a[i] + b[i] + g; if (p % n != c[i]) return true; g = p / n; p %= n; } return false; } bool modcheck() { int i, p, p1, p2, g = 0; //a + b = c, all know for (i = n - 1; i >= 0; i --) { if (a[i] >= n || b[i] >= n || c[i] >= n) continue; p = (a[i] + b[i]) % n; if (!(p == c[i] || (p + 1) % n == c[i])) return true; } //a + ? = c for (i = n - 1; i >= 0; i --) { if (!(a[i] < n && c[i] < n && b[i] >= n)) continue; p1 = (c[i] - a[i] + n) % n; p2 = (p1 - 1) % n; if (used[p1] && used[p2]) return true; } //? + b = c for (i = n - 1; i >= 0; i --) { if (!(a[i] >= n && c[i] < n && b[i] < n)) continue; p1 = (c[i] - b[i] + n) % n; p2 = (p1 - 1) % n;

第 131 页 | 共 209 页

NOIP 2004 提高组 解题报告

if (used[p1] && used[p2]) return true; } //a + b = ? for (i = n - 1; i >= 0; i --) { if (!(a[i] < n && b[i] < n && c[i] >= n)) continue; p1 = (a[i] + b[i]) % n; p2 = (p1 + 1) % n; if (used[p1] && used[p2]) return true; } return false; } void dfs(int l) { int i; string A, B, C; if (finish) return; if (bad()) return; if (modcheck()) return; if (l == n) { outsol(); return; } for (i = n - 1; i >= 0; i --) if (!used[i]) { used[i] = true; A = a; B = b; C = c; a = change(A, word[l], i); b = change(B, word[l], i); c = change(C, word[l], i); stk[l] = i; dfs(l + 1); used[i] = false; a = A; b = B; c = C; } } int main() { init(); pre_doing(); dfs(0); return 0; }

第 132 页 | 共 209 页

NOIP 2004 提高组 解题报告

<小结> 搜索题的框架往往不难找到, 关键就是在搜索的优化上, 本文的主要篇幅也就是讨 论了几种有效的优化。搜索问题的优化更多的需要选手的经验和思考、分析问题的能力,所 以搜索剪枝也是竞赛中经久不衰的经典问题。

第 133 页 | 共 209 页

NOIP 2005 普及组 复赛试题

NOIP2005 复赛普及组试题
试题来源?http://www.oifans.cn

第十一届全国青少年奥林匹克信息学联赛复赛普及组试题 (普及组 三小时完成) 陶陶摘苹果 (apple.pas/c/cpp) 【问题描述】 陶陶家的院子里有一棵苹果树,每到秋天树上就会结出 10 个苹果。苹果成熟的时候,陶陶就会 跑去摘苹果。陶陶有个 30 厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上 再试试。 现在已知 10 个苹果到地面的高度,以及陶陶把手伸直的时候能够达到的最大高度,请帮陶陶算 一下她能够摘到的苹果的数目。假设她碰到苹果,苹果就会掉下来。 【输入文件】 输入文件 apple.in 包括两行数据。第一行包含 10 个 100 到 200 之间(包括 100 和 200)的 整数 (以厘米为单位) 分别表示 10 个苹果到地面的高度, 两个相邻的整数之间用一个空格隔开。 第二行只包括一个 100 到 120 之间(包含 100 和 120)的整数(以厘米为单位) ,表示陶陶把 手伸直的时候能够达到的最大高度。 【输出文件】 输出文件 apple.out 包括一行,这一行只包含一个整数,表示陶陶能够摘到的苹果的数目。 【样例输入】 100 200 150 140 129 134 167 198 200 111 110 【样例输出】 5 校门外的树 (tree.pas/c/cpp) 【问题描述】

第 134 页 | 共 209 页

NOIP 2005 普及组 复赛试题

某校大门外长度为 L 的马路上有一排树,每两棵相邻的树之间的间隔都是 1 米。我们可以把马 路看成一个数轴, 马路的一端在数轴 0 的位置, 另一端在 L 的位置; 数轴上的每个整数点, 即 0, 1,2,……,L,都种有一棵树。 由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知 任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域 中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上还有多 少棵树。 【输入文件】 输入文件 tree.in 的第一行有两个整数 L(1 <= L <= 10000)和 M(1 <= M <= 100) , L 代表马路的长度,M 代表区域的数目,L 和 M 之间用一个空格隔开。接下来的 M 行每行包含 两个不同的整数,用一个空格隔开,表示一个区域的起始点和终止点的坐标。 【输出文件】 输出文件 tree.out 包括一行,这一行只包含一个整数,表示马路上剩余的树的数目。 【样例输入】 500 3 150 300 100 200 470 471 【样例输出】 298 【数据规模】 对于 20%的数据,区域之间没有重合的部分; 对于其它的数据,区域之间有重合的情况。 采药 (medic.pas/c/cpp) 【问题描述】

第 135 页 | 共 209 页

NOIP 2005 普及组 复赛试题

辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望 的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的 山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有 它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明 的孩子,你应该可以让采到的草药的总价值最大。” 如果你是辰辰,你能完成这个任务吗? 【输入文件】 输入文件 medic.in 的第一行有两个整数 T(1 <= T <= 1000)和 M(1 <= M <= 100) , 用一个空格隔开,T 代表总共能够用来采药的时间,M 代表山洞里的草药的数目。接下来的 M 行每行包括两个在 1 到 100 之间(包括 1 和 100)的整数,分别表示采摘某株草药的时间和这 株草药的价值。 【输出文件】 输出文件 medic.out 包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草 药的最大总价值。 【样例输入】 70 3 71 100 69 1 12 【样例输出】 3 【数据规模】 对于 30%的数据,M <= 10; 对于全部的数据,M <= 100。 循环 (circle.pas/c/cpp)

第 136 页 | 共 209 页

NOIP 2005 普及组 复赛试题

【问题描述】 乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天,他突然对数的正整数 次幂产生了兴趣。 众所周知,2 的正整数次幂最后一位数总是不断的在重复 2,4,8,6,2,4,8,6……我们说 2 的正整数次幂最后一位的循环长度是 4 (实际上 4 的倍数都可以说是循环长度, 但我们只考虑 最小的循环长度) 。类似的,其余的数字的正整数次幂最后一位数也有类似的循环现象:

循环 循环长度 2 2、4、8、6 4 3 3、9、7、1 4 4 4、6 2 5 5 1 6 6 1 7 7、9、3、1 4 8 8、4、2、6 4 9 9、1 2

第 137 页 | 共 209 页

NOIP 2005 普及组 复赛试题

这时乐乐的问题就出来了:是不是只有最后一位才有这样的循环呢?对于一个整数 n 的正整数 次幂来说,它的后 k 位是否会发生循环?如果循环的话,循环长度是多少呢? 注意: 1. 如果 n 的某个正整数次幂的位数不足 k,那么不足的高位看做是 0。 2. 如果循环长度是 L,那么说明对于任意的正整数 a,n 的 a 次幂和 a + L 次幂的最后 k 位 都相同。 【输入文件】 输入文件 circle.in 只有一行,包含两个整数 n(1 <= n < 10100)和 k(1 <= k <= 100) , n 和 k 之间用一个空格隔开,表示要求 n 的正整数次幂的最后 k 位的循环长度。 【输出文件】 输出文件 circle.out 包括一行,这一行只包含一个整数,表示循环长度。如果循环不存在,输 出-1。 【样例输入】 32 2 【样例输出】 4 【数据规模】 对于 30%的数据,k <= 4; 对于全部的数据,k <= 100。

第 138 页 | 共 209 页

NOIP 2005 提高组 复赛试题

NOIP2005 复赛提高组试题
第十一届全国青少年奥林匹克信息学联赛复赛提高组试题 (提高组 三小时完成) 试题来源依然是?http://www.oifans.cn/ 谁拿了最多奖学金 (scholar.pas/c/cpp) 【问题描述】 某校的惯例是在每学期的期末考试之后发放奖学金。 发放的奖学金共有五种, 获取的条件各自不 同: 1) 院士奖学金,每人 8000 元,期末平均成绩高于 80 分(>80) ,并且在本学期内发表 1

篇或 1 篇以上论文的学生均可获得; 2) 五四奖学金,每人 4000 元,期末平均成绩高于 85 分(>85) ,并且班级评议成绩高于

80 分(>80)的学生均可获得; 3) 4) 得; 5) 班级贡献奖,每人 850 元,班级评议成绩高于 80 分(>80)的学生干部均可获得; 成绩优秀奖,每人 2000 元,期末平均成绩高于 90 分(>90)的学生均可获得; 西部奖学金,每人 1000 元,期末平均成绩高于 85 分(>85)的西部省份学生均可获

只要符合条件就可以得奖, 每项奖学金的获奖人数没有限制, 每名学生也可以同时获得多项奖学 金。例如姚林的期末平均成绩是 87 分,班级评议成绩 82 分,同时他还是一位学生干部,那么 他可以同时获得五四奖学金和班级贡献奖,奖金总数是 4850 元。 现在给出若干学生的相关数据, 请计算哪些同学获得的奖金总数最高 (假设总有同学能满足获得 奖学金的条件) 。 【输入文件】 输入文件 scholar.in 的第一行是一个整数 N(1 <= N <= 100) ,表示学生的总数。接下来的 N 行每行是一位学生的数据,从左向右依次是姓名,期末平均成绩,班级评议成绩,是否是学生 干部,是否是西部省份学生,以及发表的论文数。姓名是由大小写英文字母组成的长度不超过 20 的字符串(不含空格) ;期末平均成绩和班级评议成绩都是 0 到 100 之间的整数(包括 0 和 100) ;是否是学生干部和是否是西部省份学生分别用一个字符表示,Y 表示是,N 表示不是; 发表的论文数是 0 到 10 的整数(包括 0 和 10) 。每两个相邻数据项之间用一个空格分隔。

第 139 页 | 共 209 页

NOIP 2005 提高组 复赛试题

【输出文件】 输出文件 scholar.out 包括三行, 第一行是获得最多奖金的学生的姓名, 第二行是这名学生获得 的奖金总数。 如果有两位或两位以上的学生获得的奖金最多, 输出他们之中在输入文件中出现最 早的学生的姓名。第三行是这 N 个学生获得的奖学金的总数。 【样例输入】 4 YaoLin 87 82 Y N 0 ChenRuiyi 88 78 N Y 1 LiXin 92 88 N N 0 ZhangQin 83 87 Y N 1 【样例输出】 ChenRuiyi 9000 28700 过河 (river.pas/c/cpp) 【问题描述】 在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙 很讨厌踩在这些石子上。 由于桥的长度和青蛙一次跳过的距离都是正整数, 我们可以把独木桥上 青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中 L 是桥的长度) 。坐标为 0 的 点表示桥的起点,坐标为 L 的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。 一次跳跃的距离是 S 到 T 之间的任意正整数(包括 S,T) 。当青蛙跳到或跳过坐标为 L 的点时, 就算青蛙已经跳出了独木桥。 题目给出独木桥的长度 L,青蛙跳跃的距离范围 S,T,桥上石子的位置。你的任务是确定青蛙要 想过河,最少需要踩到的石子数。 【输入文件】

第 140 页 | 共 209 页

NOIP 2005 提高组 复赛试题

输入文件 river.in 的第一行有一个正整数 L(1 <= L <= 109) ,表示独木桥的长度。第二行有 三个正整数 S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其 中 1 <= S <= T <= 10,1 <= M <= 100。第三行有 M 个不同的正整数分别表示这 M 个 石子在数轴上的位置(数据保证桥的起点和终点处没有石子) 。所有相邻的整数之间用一个空格 隔开。 【输出文件】 输出文件 river.out 只包括一个整数,表示青蛙过河最少需要踩到的石子数。 【样例输入】 10 235 23567 【样例输出】 2 【数据规模】 对于 30%的数据,L <= 10000; 对于全部的数据,L <= 109。 篝火晚会 (fire.pas/c/cpp) 【问题描述】 佳佳刚进高中,在军训的时候,由于佳佳吃苦耐劳,很快得到了教官的赏识,成为了“小教官”。 在军训结束的那天晚上, 佳佳被命令组织同学们进行篝火晚会。 一共有 n 个同学, 编号从 1 到 n。 一开始,同学们按照 1,2,……,n 的顺序坐成一圈,而实际上每个人都有两个最希望相邻的 同学。如何下命令调整同学的次序,形成新的一个圈,使之符合同学们的意愿,成为摆在佳佳面 前的一大难题。 佳佳可向同学们下达命令,每一个命令的形式如下: (b1, b2,... bm -1, bm) 这里 m 的值是由佳佳决定的, 每次命令 m 的值都可以不同。 这个命令的作用是移动编号是 b1, b2,…… bm –1,bm 的这 m 个同学的位置。要求 b1 换到 b2 的位置上,b2 换到 b3 的位置 上,……,要求 bm 换到 b1 的位置上。

第 141 页 | 共 209 页

NOIP 2005 提高组 复赛试题

执行每个命令都需要一些代价。我们假定如果一个命令要移动 m 个人的位置,那么这个命令的 代价就是 m。我们需要佳佳用最少的总代价实现同学们的意愿,你能帮助佳佳吗? 【输入文件】 输入文件 fire.in 的第一行是一个整数 n(3 <= n <= 50000) ,表示一共有 n 个同学。其后 n 行每行包括两个不同的正整数,以一个空格隔开,分别表示编号是 1 的同学最希望相邻的两个 同学的编号,编号是 2 的同学最希望相邻的两个同学的编号,……,编号是 n 的同学最希望相邻 的两个同学的编号。 【输出文件】 输出文件 fire.out 包括一行,这一行只包含一个整数,为最小的总代价。如果无论怎么调整都 不能符合每个同学的愿望,则输出-1。 【样例输入】 4 34 43 12 12 【样例输出】 2 【数据规模】 对于 30%的数据,n <= 1000; 对于全部的数据,n <= 50000。 等价表达式 (equal.pas/c/cpp) 【问题描述】 明明进了中学之后,学到了代数表达式。有一天,他碰到一个很麻烦的选择题。这个题目的题干

第 142 页 | 共 209 页

NOIP 2005 提高组 复赛试题

中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的要 求是判断选项中哪些代数表达式是和题干中的表达式等价的。 这个题目手算很麻烦, 因为明明对计算机编程很感兴趣, 所以他想是不是可以用计算机来解决这 个问题。假设你是明明,能完成这个任务吗? 这个选择题中的每个表达式都满足下面的性质: 1. 表达式只可能包含一个变量?a?。 2. 表达式中出现的数都是正整数,而且都小于 10000。 3. 表达式中可以包括四种运算?+?(加) ,?-?(减) ,?*?(乘) ,?^?(乘幂) ,以及小括号?(?,?)?。 小括号的优先级最高,其次是?^?,然后是?*?,最后是?+?和?-?。?+?和?-?的优先级是相同的。相 同优先级的运算从左到右进行。 (注意:运算符?+?,?-?,?*?,?^?以及小括号?(?,?)?都是英文字 符) 4. 幂指数只可能是 1 到 10 之间的正整数(包括 1 和 10) 。 5. 表达式内部,头部或者尾部都可能有一些多余的空格。 下面是一些合理的表达式的例子: ((a^1) ^ 2)^3,a*a+a-a,((a+a)),9999+(a-a)*a,1 + (a -1)^3,1^10^9…… 【输入文件】 输入文件 equal.in 的第一行给出的是题干中的表达式。 第二行是一个整数 n (2 <= n <= 26) , 表示选项的个数。后面 n 行,每行包括一个选项中的表达式。这 n 个选项的标号分别是 A,B, C,D…… 输入中的表达式的长度都不超过 50 个字符, 而且保证选项中总有表达式和题干中的表达式是等 价的。 【输出文件】 输出文件 equal.out 包括一行,这一行包括一系列选项的标号,表示哪些选项是和题干中的表 达式等价的。选项的标号按照字母顺序排列,而且之间没有空格。 【样例输入】 ( a + 1) ^2 3

第 143 页 | 共 209 页

NOIP 2005 提高组 复赛试题

(a-1)^2+4*a a + 1+ a a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a 【样例输出】 AC 【数据规模】 对于 30%的数据,表达式中只可能出现两种运算符?+?和?-?; 对于其它的数据,四种运算符?+?,?-?,?*?,?^?在表达式中都可能出现。 对于全部的数据,表达式中都可能出现小括号?(?和?)?。

第 144 页 | 共 209 页

NOIP 2006 提高组 解题报告

NOIP2005 信息学奥林匹克分区联赛

解题报告
感谢原作团队?[麓山 NOI 战队]
第一题:谁拿了最多的奖学-Scholar [问题评估] 这个题目据问题本身而言是相当简单的,没有牵涉到过多的算法,属于普及型试题。同时也是对实际 问题一种分析和判断。总的来看,本题在方向上,向现实问题迈出了一步,是信息学和生活有了更多的联 系。 问题的算法是模拟。当中唯一的难点就是数据处理,考察点为数据库的建立和统计。 [程序实现] 由于程序数据范围只有 100,当中不牵涉到数据移动,所以用一个纪录型数组,或者多个数组均可, 在这里我们使用纪录型来描述。 对于输入数据有两种方式来实现。 法一〉逐个字符累加。 首先定义 C:char; 然后利用 Until c=‘ ’;作为终止符,将读入的字符连接存储到 a[i].name 中。 代码为: Repeat read(c); a[i].name:=a[i].name+c; until c=’ ‘; a[i].name:=copy(a[i].name,1,length(a[i].s)-1); 这样做的好处是,后面的值可以直接用 read 语句读入。但是最后一个值后,要记得 readln; 法二〉一次读入,然后分离。 这样做需要逐个分离,对本题来说稍显复杂,但对 NOIP 来说此方法必须掌握,有的时候 一定要用。 具体实现,读入一个字符串 S。利用 pos(‘ ‘,s);找出空格位置。再利用 Copy 函数,和 Val 函数进行截取,和转换。 部分代码:(s:string;j,ok:integer) readln(s); j:=pos(‘ ‘,s); a[i].name:=copy(s,1,j-1); s:= copy(s,j+1,50); //当长度〉字符串长度是,为后面全部截取。 j:=pos(‘ ‘,s); Val(copy(s,1,j-1),a[i].qp,ok); s:= copy(s,j+1,50); ….. 对于符号用 if 语句作一下判断就是了,太 easy 不写了,后面还有几个值,用同样方法处理 就可以了。 以上完成了数据库的建库工作,后面是统计,当然,我们在没读完一行数据后就可进行统计。用 If 语句判断他是否能得到相应的分值即可。分 5 条 If 语句写,每回可以就加入相应的分值。 将每个的分值汇总计入到总数变量 ZD 当中。与当前最大值进行比较,得到 Max 对应的 I 值。后面就 是输出的问题了。 [小结、注意] 本题为简单题,只要思路明确清晰,就可 AC。时间复杂度 O(n)。但有一个细节,ZD 变量必须定义

第 145 页 | 共 209 页

NOIP 2006 提高组 解题报告 Longint 或以上类型否则会 Error201 的。 第二题 过河-River [问题分析] 此题初看是一个典型的搜索题。从河的一侧到河的另一侧,要找最少踩到的石头数。但从数据范围来 看。1..109 长度的桥。就算是 O(n)的算法也不能在一秒内出解。 如果搜索石子,方法更困难。这要考虑到前面以及后面连续的石子。若换一种方法。用动态规划,以 石子分阶段的一维动规,时间复杂度是 O(n2)。最多也只有 100×100 的时间。但是这样分状态就十分复杂。 因为石头的分布是没有任何规律,而且会有后效性。 这样只好有回到搜索。搜索石子会和动规一样没有规律。我们一桥的长度为对象进行搜索,然后再加 上一个巧妙的剪枝就可以在很短的时间内出解。可以号称为 O(m2)。[批注:号称一词已成为湖南 OI 本世 纪流行词汇 ] [题目实现] 先以时间为对象进行搜索。时间复杂度为 O(L)。从桥的一侧到另一侧,中间最多只有 100 个石子。假 设桥长为最大值(109),石头数也为最大值(100)。这样中间一定会有很多“空长条” (两个石子中的空地), 处理时把这些跳过,就只会有 M 次运算。关键是找出每一个可以跳过的“空长条” 。 我们可以先把青蛙可以跳出的所有可能求出,然后就可以求出可以忽略的“空长条” 。

[特殊算法] a[i]:前 i 个坐标中石子最小个数,初始为第 i 个坐标的石子个数 b[i]:第 i 个石子坐标 动规 a[0]=0; 对 n>=t a[n]=min{a[n]+a[n-s],a[n]+a[n-s-1], ...,a[n]+a[n-t]} 对 s=<n<t a[n]=max{a[n]+a[n-s],a[n]+a[n-s-1],...,a[n]+a[0]} 但由于 n 较大直接动规会超时。所以要将 n 压缩 查看坐标, 可以发现, 如果 b[i]-b[i-1]>t, 显然对于 b[i-1]+t<n<b[i], a[n]总是等于 a[b[i-1]]..a[b[i-1]+t]中的数, 因此可对其进行压缩

相关文章:
1995-2008 历届NOIP试题及详解
1995-2008 历届NOIP试题及详解_学科竞赛_高中教育_教育专区。对历届(1995-2008)NOIP试题、数据及解题报告的整理。个人比较懒,对于找不到的资料就扔掉了,请谅解~ ...
1995—2008复赛试题
1995-2008复赛试题及解析 25页 10财富值 1995-2008全国初中数学联赛... 78页...NOIP+提高组复赛试题汇编(... 32页 免费 历届全国初中数学联赛试题... 2页 ...
历届题_2008年解析
历届题_2008解析 noip2008noip2008隐藏>> 2008 年普及级解析 一、 3、图灵奖(A.M. Turing Award) ,由美国计算机协会(ACM)于 1966 年设立, 又叫“A.M....
中科院地理所考博1995~2008真题GIS
中科院地理所考博1995~2008真题GIS_研究生入学考试_高等教育_教育专区。1995 年中科院博士入学试题 一, 简述题(40 分) 1. 地理信息系统的主要功能. 2. 图形数据...
noip1999-2008试题大全5
noip1999-2008试题大全5_IT/计算机_专业资料。noip1999-2008试题大全2007 奖学金 Time Limit: 1000MS Memory Limit: 65536K 题目描述某小学最近得到了一笔赞助, ...
2008年初赛试题及答案
第十四届全国青少年信息学奥林匹克联赛初赛试题( 提高组 Pascal 语言 二小时完成...NOIP2008 年提高组(Pascal 语言)参考答案与评分标准 一、单项选择题: (每题 ...
南开大学1995-2008年研究生招生考试西方经济学试题
南开大学1995-2008年研究生招生考试西方经济学试题 隐藏>> 南开大学 1995 年研究生招生考试西方经济学试题 一、判断对错并改错(5 分) 1.在完全竞争条件下,厂商...
NOIP1995年普及组复赛试题
NOIP1995年普及组复赛试题_IT/计算机_专业资料。NOI’95 “同创杯”全国青少年信息学(计 算机)奥林匹克竞赛 分区联赛复赛试题(初中组) (上机编程,完成时间:210 ...
noip竞赛试题1995题目
关键词:nuip竞赛试题 同系列文档 朝鲜历届领导人资料 朝鲜现状 为什么南北朝鲜会分裂 朝鲜的近代史1/2 相关文档推荐 noip 1995 附答案 10页 免费 noip竞赛试题200...
第一届(1995年)NOIP联赛普及组初赛试题(附答案)
第14届(2008年)NOIP联赛普... 6页 免费 第七届(2001年)NOIP联赛普... 7...第一届(1995年)NOIP联赛普及组初赛试题(附答案)第一届(1995年)NOIP联赛普及组...
更多相关标签:
noip历届试题 | noip1995 | noip2016初赛试题 | noip2016复赛试题 | noip初赛试题 | noip提高组复赛试题 | noip试题 | noip历年试题 |