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

1995-2008复赛试题及解析


NOIP1995 年复赛试题
1. 设有下列的算式:求出□中的数字,并打印出完整的算式来。 8 0 9 ------------□□) □□□□ □□ ------------□□□ □□□ ------------1 2. 方阵填数:在一个 N ? N 的方阵中,填入 1,2,??N ? N 个数,并要求构成如下的格式: 例: N=5 13 14 12 23 11 2

2 10 21 9 8 N=6 16 17 15 30 14 29 13 28 12 27 11 10

15 24 25 20 7

16 17 18 19 6

1 2 3 4 5

18 31 36 35 26 9

19 32 33 34 25 8

20 21 22 23 24 7

1 2 3 4 5 6

3. 若将一个正整数化为二进制数,在此二进制数中,我们将数字 1 的个数多于数字 0 的个数的这类二进 制数称为 A 类数,否则就称其为 B 类数。 例如: (13)10=(1101)2 (10)10=(1010)2 (24)10=(11000)2 其中 1 的个数为 3,0 的个数为 1,则称此数为 A 类数; 其中 1 的个数为 2,0 的个数也为 2,称此数为 B 类数; 其中 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[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 中的原数据。 5. 灯的排列问题:设在一排上有 N 个格子(N≤20) ,若在格子中放置有不同颜色的灯,每种灯的个数记 为 N1,N2,??Nk(k 表示不同颜色灯的个数) 。 放灯时要遵守下列规则:同一种颜色的灯不能分开;不同颜色的灯之间至少要有一个空位置。 例如:N=8(格子数) 放置的方法有: R R R R=2(红灯数) R-B 顺序 R R R R R R R R R
1

此时,数组 A 的编码定义如下:

B=3(蓝灯数) B B B B B B B B B B B B B B B B B

B

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

NOIP1996 年复赛试题
1.编制一个乘法运算的程序(20 分) 从键盘读入 2 个 100 以内的正整数,进行乘法运算并以竖式输出。 例如,输入格式:8913 输出格式: 89 × 13 267 89 1157 2.输入三个自然数 N,i,j (1<=i<=N,1<=j<=N) ,输出在一个 N*N 格的棋盘中,与格子(i,j)同行、 同列、同一对角线的所有格子的位置。 (20 分) 如:n=4,i=2,j=3 表示了棋盘中的第二行第三列的格子,如下图: 第一列 第二列 第三列 第四列 第1行 第2行 (2,3) 第3行 第4行 又如,输入格式:16 8 输出格式: × 16 8 128

当 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)
2

{同一行上格子的位置} {同列列上格子的位置} {左上到右下对角线上的格子的位置} {左下到右上对角线上的格子的位置}

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’ ,则插入 插入后:’This ids a book.’ 在最后一个字符的前面,如上例中: 串:’This is 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

NOIP1997 年复赛试题
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 个。
3

程序要求:输入:n 和 m 如上例: 输入:2 3 a b d f (1)a<f<i; (2)b<d, g<h, c<e g h c e

输出:正方形的个数与长方形的个数 输出:8,10

2.将 1,2,···,9 共 9 个数排成下列形态的三角形。 ··· (30%)

i

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

(3)a+b+d+f=f+g+h+i=i+e+c+a=P 程序要求: 根据输入的边长之和 P 输出所有满足上述条件的三角形的个数以及其中的一种方案。 3.设有一个 N*M(l≤ N≤50, l≤ M≤ 50)的街道(如下图)(40%) : 北 5 B (9, 5) 4 东 * * * * * * 3 西 2 * * * * * * 1 1 2 3 4 5 6 7 8 9 A(1,1) 南 规定行人从 A(1,1)出发,在街道上只能向东或北方向行走。 如下为 N=3,M=3 的街道图,从 A 出发到达 B 共有 6 条可供行走的路径: A6 A7 B(N,M)

1.A-A1-A2-A5-B 2. A-A1-A4-A5-B 3. A-A1-A4-A7-B A3 A4 A5 4. A-A3-A4-A5-B 5. A-A3-A4-A7-B A A1 A2 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 的路径的条数。

NOIP1998 年复赛试题
1.将 1,2,?,9 共 9 个数分成三组,分别组成三个三位数,且使这三个三位数构成 1:2:3 的比例,试求出所有满足条件的三个三位数。 例如:三个三位数 192,384,576 满足以上条件。
4

{30%}

2.用高精度计算出 S=1!+2!+3!+?+n! (n≤50) 其中“! ”表示阶乘,例如:5!=5*4*3*2*1。 137=2 +2 +2
7 3 0 b

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

3.任何一个正整数都可以用 2 的幂次方表示。例如: 同时约定方次用括号来表示,即 a 可表示为 a(b) 。 由此可知,137 可表示为: 进一步:7= 2 +2+2 又如:
2 0 1

2(7)+2(3)+2(0)
0

(2 用 2 表示) 3=2+2 1315=2
10 8 5

所以最后 137 可表示为:

2(2(2)+2+2(0) )+2(2+2(0) )+2(0) +2 +2 +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 表示(在表示中不能有空格)

NOIP1999 年复赛试题
第一题 题的: 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 ? 1/2 1/3 1/4 1/5 ? 2/2 2/3 2/4 ? 3/2 3/3 ? 4/2 ? Cantor 表(30 分)

现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命

5/1 ?

我们以 Z 字形给上表的每一项编号。第一项是 1/1, 然后是 1/2,2/1,3/1,2/2,? 输入:整数 N(1≤N≤10000000) 样例: 第二题 回文数(30 分) INPUT N=7

输出:表中的第 N 项 OUTPUT 1/4

若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。 例如:给定一个 10 进制数 56,将 56 加 56(即把 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
5

OUTPUT 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 每升汽油价格 Pi 2.9 2.2

油站号 I 1 2 OUTPUT

离出发点的距离 Di 102.0 220.0

26.95(该数据表示最小费用)

NOIP2000 年复赛试题
题一 计算器的改良 (18 分)

问题描述:NCL 是一家专门从事计算器改良与升级的实验室,最近该实验室收到了某公司所委托的一个任 务:需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交给了一个刚进入的 新手 ZL 先生。为了很好的完成这个任务,ZL 先生首先研究了一些一元一次方程的实例: 4+3x=8 6a-5+1=2-2a -5+12y=0 ZL 先生被主管告之,在计算器上键入的一个一元一次方程中,只包含整数、小写字母及+、-、=这 三个数学符号(当然,符号“─”既可作减号,也可作负号) 。方程中并没有括号,也没有除号,方程中 的字母表示未知数。 问题求解:编写程序,解输入的一元一次方程, 将解方程的结果(精确至小数点后三位)输出至屏幕。你可 假设对键入的方程的正确性的判断是由另一个程序员在做,或者说可认为键入的一元一次方程均为合法 的,且有唯一实数解。 题二.税收与补贴问题 样例:输入:6a-5+1=2-2a (20 分) 输出:a=0.750

问题描述:每样商品的价格越低,其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量 (产品不会低于成本销售) ,并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后,销 量以某固定数值递减。 (我们假设价格及销售量都是整数) 对于某些特殊商品, 不可能完全由市场去调节其价格。 这时候就需要政府以税收或补贴的方式来控制。 (所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币) 问题求解: 你是某家咨询公司的项目经理,现在你已经知道政府对某种商品的预期价格,以及在各种 价位上的销售情况。要求你确定政府对此商品是应收税还是补贴的最少金额(也为整数) ,才能使商家在 这样一种政府预期的价格上,获取相对其他价位上的最大总利润。

总利润

= 单位商品利润 * 销量

单位商品利润 = 单位商品价格 – 单位商品成本 (– 税金 or + 补贴)
输入:输入的第一行为政府对某种商品的预期价,第二行有两个整数,第一个整数为商品成本,第二个整 数为以成本价销售时的销量售,以下若干行每行都有两个整数,第一个为某价位时的单价,第二个为此时
6

的销量,以一行-1,-1 表示所有已知价位及对应的销量输入完毕,输入的最后一行为一个单独的整数表示 在已知的最高单价外每升高一块钱将减少的销量。 输出:输出有两种情况:若在政府预期价上能得到最大总利润,则输出一个单独的整数,数的正负表示是 补贴还是收税,数的大小表示补贴或收税的金额最小值。若有多解,取绝对值最小的输出。 如在政府预期价上不能得到最大总利润,则输出“NO SOLUTION”. 样例: 输入 31 28 130 30 120 31 110 -1 –1 15 输出 题三 4 乘积最大 (26 分)

问题描述:今年是国际数学联盟确定的“2000——世界数学年” ,又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友 XZ 也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目: 设有一个长度为 N 的数字串,要求选手使用 K 个乘号将它分成 K+1 个部分,找出一种分法,使得这 K+1 个 部分的乘积能够为最大。 同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子: 有一个数字串:312, 当 N=3,K=1 时会有以下两种分法: 1) 3*12=36 2) 31*2=62 这时,符合题目要求的结果是:31*2=62 现在,请你帮助你的好朋友 XZ 设计一个程序,求得正确的答案。 输入:程序的输入共有两行: 第一行共有 2 个自然数 N,K(6≤N≤40,1≤K≤6) 第二行是一个长度为 N 的数字串。 输出:结果显示在屏幕上,相对于输入,应输出所求得的最大乘积(一个自然数) 。 样例: 输入 4 2 1231 输出 题四. 62 单词接龙 (36 分)

问题描述: 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一 个开头的字母,要求出以这个字母开头的最长的“龙” (每个单词都最多在“龙”中出现两次) ,在两个单 词相连时,其重合部分合为一部分,例如 beast 和 astonish,如果接成一条龙则变为 beastonish,另外 相邻的两部分不能存在包含关系,例如 at 和 atide 间不能相连。 输入:输入的第一行为一个单独的整数 n(n<=20)表示单词数,以下 n 行每行有一个单词,输入的最后一行 为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
7

输出: 样例: 输入 5 at touch cheat choose tact a 输出

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

23

(连成的“龙”为 atoucheatactactouchoose)

NOIP2001 年复赛试题
题一:数的计数 (20 分) 问题描述:我们要求找出具有下列性质数的个数(包含输入的自然数 n);先输入一个自然数 n(n≤1000), 然后对此自然数按照如下方法进行处理 1. 不作任何处理; 2. 茬它的左边加上一个自然数,但该自然数不能超过原数的一半; 3.加上数后,继续按此规则进行处理,直到不能再而 自然数为止。 [样例] 输入:6 满足条件的数为 6 6 26 126 36 136 输出:6 题二:最大公约数与最小公倍数问题 (20 分) 问题描述:输入二个正整数 x0,y0(2≤x0≤100000,2≤y0≤1000000),求出满足下列条件的 P、Q 的个数。 条件:1.. P、Q 是正整数;2. 要求 P、Q 以 xO 为最大公约数,以 yO 为最小公倍数。 试求,满足条件的所有可能的两个正整数的个数。 [样例] 输入:x0=3 输出:4 说明:(不用输出)此时的 P Q 分别为,满足条件的所有可能的两个正整数的个数共 4 种。 3 60 15 12 12 15 60 3
8

(此部分不必输出)

y0=60

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

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

接下来的问题就是判断素数,判断一个整数 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 做特殊处理。 题三: 产生数 [问题描述]:给出一个整数 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 for j ? 1 to n do a[i, j] = a[i, j] or (a[i, k] and a[k, j]) 最后值得注意的是当 n 很大时输出可能会超过 Comp 类型的范围,所以要使用高精度乘法,由于高精 度算法是信息学竞赛中的基础,这里就不在详述。 题四: 过河卒 [问题描述]:棋盘上 A 点有一个过河卒,需要走到目标 B 点。卒行走的规则:可以向下、或者向右。 同时在棋盘上 C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。 棋盘用坐标表示,A 点(0,0)、B 点(n, m) (n,m 为不超过 20 的整数),同样马的位置坐标是需要给出的。现 在要求你计算出卒从 A 点能够到达 B 点的路径的条数 [问题分析]: 这是一道老得不能再老的题目了,很多书上都有类似的题目,NOIp97 普及组的最后一 题就和本题几乎一模一样。有些同学由于没见过与之类似的题目,在比赛时用了搜索,当 n 到 14,15 左 右就会超时,其实,本题稍加分析,就能发现:要到达棋盘上的一个点,只能从左边过来或是从上面下来,
10

所以根据加法原理,到达某一点的路径数目,等于到达其相邻上,左两点的路径数目之和,因此我们可以 使用逐列(或逐行)递推的方法来求出从起始顶点到重点的路径数目,即使有障碍(我们将马的控制点称 为障碍) ,这一方法也完全适用,只要将到达该点的路径数目置为 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] { g[x,y] = 1 } {i > 0, g[x,y] = 0} {j > 0, g[x,y] = 0}

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

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

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 分制下的结果,两部分之间由一个空行分隔。 【输入样例】 【输出样例】 11:0 11:0 1:1 21:0 2:1
11

WWWWWWWWWWWWWWWWWWWW WWLWE

题二、数字游戏(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 行每行有个整数,其绝 对值不大于 10 ,按顺序给出圈中的数字,首尾相接。 【输出格式】输出文件有两行,各包含一个非负整数。第一行是你程序得到的最小值,第二行是最大值。 【输入样例】 4 2 4 3 -1 2 【输出样例】 7 81 题三、栈(Stack.pas) 【问题背景】栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。 栈有两种最重要的操作,即 pop(从栈顶弹出一个元素)和 push(将一个元素进栈) 。 栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一 个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。 【问题描述】
4

-1

输出序列

尾端 头端

头端

1

2

3

操作数序列

栈A
12

宁宁考虑的是这样一个问题:一个操作数序列,从 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 3 1 2 3 1

1 1

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

1279

NOIP2004 年复赛试题
1.不高兴的津津 (unhappy.pas/dpr/c/cpp) 【问题描述】津津上初中了。妈妈认为津津应该更加用功学习,所以津津除了上学之外,还要参加妈妈为 她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个 小时就会不高兴,而且上得越久就会越不高兴。假设津津不会因为其它事不高兴,并且她的不高兴不会持 续到第二天。请你帮忙检查一下津津下周的日程安排,看看下周她会不会不高兴;如果会的话,哪天最不 高兴。 【输入文件】输入文件 unhappy.in 包括七行数据,分别表示周一到周日的日程安排。每行包括两个小于 10 的非负整数,用空格隔开,分别表示津津在学校上课的时间和妈妈安排她上课的时间。 【输出文件】输出文件 unhappy.out 包括一行,这一行只包含一个数字。如果不会不高兴则输出 0,如果 会则输出最不高兴的是周几(用 1, 2, 3, 4, 5, 6, 7 分别表示周一,周二,周三,周四,周五,周六, 周日) 。如果有两天或两天以上不高兴的程度相当,则输出时间最靠前的一天。 【样例输入】 5 3 6 2 7 2 5 3 5 4 0 4 0 6 【样例输出】 2.花生采摘 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
14

行,每行包括 N 个非负整数,也用空格隔开;第 i + 1 行的第 j 个整数 Pij(0 <= Pij <= 500)表示花生 田里植株(i, j)下花生的数目,0 表示该植株下没有花生。 【输出文件】输出文件 peanuts.out 包括一行,这一行只包含一个整数,即在限定时间内,多多最多可以 采到花生的个数。 【样例输入 1】 6 7 21 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 【样例输出 1】 【样例输入 2】 6 7 20 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 【样例输出 2】 28 3.FBI 树 (fbi.pas/dpr/c/cpp) 【问题描述】我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为 B 串,全“1”串称为 I 串,既含“0”又含“1”的串则称为 F 串。 FBI 树是一种二叉树[1], 它的结点类型也包括 F 结点, 结点和 I 结点三种。 B 由一个长度为 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。
15

37

4.火星人

(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 1 132 2 213 3 231 4 312 5 321 6

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指,科学家会告诉你要 加上去的很小的数。你的任务是,把火星人用手指表示的数与科学家告诉你的数相加,并根据相加的结果 改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。 【输入文件】输入文件 martian.in 包括三行,第一行有一个正整数 N,表示火星人手指的数目(1 <= N <= 10000) 。第二行是一个正整数 M,表示要加上去的小整数(1 <= M <= 100) 。下一行是 1 到 N 这 N 个整数 的一个排列,用空格隔开,表示火星人手指的排列顺序。 【输出文件】输出文件 martian.out 只有一行,这一行含有 N 个整数,表示改变后的火星人手指的排列顺 序。每两个相邻的数中间用一个空格分开,不能有多余的空格。 【样例输入】 5 3 1 2 3 4 5 【样例输出】 1 2 4 5 3 【数据规模】对于 30%的数据,N<=15;对于 60%的数据,N<=50;对于全部的数据,N<=10000;

NOIP2005 年复赛试题
1.陶陶摘苹果 (apple.pas/c/cpp)

【问题描述】陶陶家的院子里有一棵苹果树,每到秋天树上就会结出 10 个苹果。苹果成熟的时候,陶陶 就会去摘苹果。陶陶有个 30 厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试。 现在已知 10 个苹果到地面的高度,以及陶陶把手伸直的时候能够达到的最大高度,请帮陶陶算一下 她能够摘到的苹果的数目。假设她碰到苹果,苹果就会掉下来。 【输入文件】输入文件 apple.in 包括两行数据。第一行包含 10 个 100 到 200 之间(包括 100 和 200)的 整数(以厘米为单位)分别表示 10 个苹果到地面的高度,两个相邻的整数之间用一个空格隔开。第二行
16

只包括一个 100 到 120 之间(包含 100 和 120)的整数(以厘米为单位) ,表示陶陶把手伸直的时候能够达 到的最大高度。 【输出文件】输出文件 apple.out 包括一行,这一行只包含一个整数,表示陶陶能够摘到的苹果的数目。 【样例输入】 100 200 150 140 129 134 167 198 200 111 110 【样例输出】 5 2.校门外的树 (tree.pas/c/cpp) 【问题描述】某校大门外长度为 L 的马路上有一排树,每两棵相邻的树之间的间隔都是 1 米。我们可以把 马路看成一个数轴, 马路的一端在数轴 0 的位置, 另一端在 L 的位置; 数轴上的每个整数点, 0, 2, 即 1, ??, 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 【样例输出】 3.采药 298 【数据规模】对于 20%的数据,区域之间没有重合的部分;对于其它的数据,区域之间有重合的情况。 (medic.pas/c/cpp) 【问题描述】辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威 望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对 他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我 会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的 草药的总价值最大。” 如果你是辰辰,你能完成这个任务吗? 【输入文件】输入文件 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
17

1 2 【样例输出】 3 【数据规模】对于 30%的数据,M <= 10;对于全部的数据,M <= 100。 4.循环 (circle.pas/c/cpp) 【问题描述】乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天,他突然对数的正整 数次幂产生了兴趣。 众所周知,2 的正整数次幂最后一位数总是不断的在重复 2,4,8,6,2,4,8,6??我们说 2 的正 整数次幂最后一位的循环长度是 4 实际上 4 的倍数都可以说是循环长度, ( 但我们只考虑最小的循环长度) 。 类似的,其余的数字的正整数次幂最后一位数也有类似的循环现象: 循环 循环长度 2:2、4、8、6 3:3、9、7、1 4:4、6 5:5 6:6 7:7、9、3、1 8:8、4、2、6 9:9、1 4 4 2 1 1 4 4 2

这时乐乐的问题就出来了: 是不是只有最后一位才有这样的循环呢?对于一个整数 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。

NOIP2006 年复赛试题
1 .明明的随机数 【 问题描述】 明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,性是用计算机生 成了 N 个 l 到 l000 之间的随机整数(N <=100 ) ,对于其中重复的数字,只保留一个,把其余相同的 数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序.然后有空去找同学做调查。 请你协助明明完成“去重”与“排序”的工作。 【 输入文件】 输入文件 random.in 有 2 行,第 1 行为 1 个正整数,表示所生成的随机数的个数:N
18

第 2 行有 N 个用空格隔开的正整数,为所产生的随机数。 【 输出文件】 输出文件 random.out 也是 2 行, 1 行为 1 个正整数 M , 第 表示不相同的随机数的个数。 第 2 行为 M 个用空格隔开的正整数,为从小到大排好序的不相同的随机数。 【 输入样例】 1O 20 40 32 67 40 20 89 300 400 15 【 输出样例】 8 1 5 20 32 40 67 89 300 400 2 .开心的金明 ( h appy . pas / c / Cpp ) 【 问题描述】 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房 间。更让他高兴的是,妈妈昨天对他说: “你的房间需要购买哪些物品,怎么布置,你说了算,只要不超 过 N 元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了.可能会超过妈妈限定的 N 元。 于是,他把每件物品规定了一个重要度,分为 5 等:用整数 1~5 表示,第 5 等最重要。他还从因特网上查 到了每件物品的价格(都是整数元) 。他希望在不超过 N 元(可以等于 N 元)的前提下,使每件物品的价 格与重要度的乘积的总和最大。 请你帮助金明设计一个满足要求的购物单。 【 输入文件】 输入文件 happy。in 的第 1 行,为两个正整数,用一个空格隔开: (总钱数 N<30000,希望购买物品的个数 m < 25,物品的价格 v < = 10000) 【 输出文件】 Happy.out 只有一个正整数,为不超过总钱数的物品的价格与其重要度的乘积之和的最大 值(<100000000) 【 输入样例】 1000 5 800 2 400 5 300 5 400 3 200 2 【 输出样例】 3900 3.【 问题描述】 Jam 是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数,而是使用小写英文字 母计数,他觉得这样做,会使世界更加丰富多彩。在他的计数法中,每个数字的位数都是相同的(使用相 同个数的字母) 英文字母按原先的顺序, , 排在前面的字母小于排在它后面的字母。 我们把这样的“数字” 称为 Jam 数字。在 Jam 数字中,每个字母互不相同,而且从左到右是严格递增的。每次还指定使用字母 的范围,例如,从 2 到 10,表示只能使用{b , c , d , e , f , g , h ,i,j}如果再规定位数为 5 , 那么,紧接在 Jam 数字“bdfij”之后的数字应该是“bdghi"。你的任务是:对于从文件读入的一个 Jam 数字,按顺序输出紧接在后面的 5 个 Jam 数字。如果后面没有那么多 Jam 数字,那么有几个就输出几个。 【 输入文件】 所给的数据都是正确的,不必验证。 【 输出文件】 输出文件 count.out 最多为 5 行,为紧接在输入的 Jam 数字后面的 5 个 Jam 数字,如果 后面没有那么多 Jam 数字,那么有几个就输出几个。每行只输出一个 Jam 数字,是由 w 个小写字母组成
19

的字符串,不要有多余的空格。 【 输入样例】 2 105 bdfij 【 输出样例】 bdghi bdqhj bdgij bdhij befqh 4、数列 给定一个正整数 k (3<=k<=15) , k 的方幂之和构成一个递增的序列, 例如, k = 3 时, 当 把所有 k 的 方幂及所有有限个互不相等的这个序列是: l , 3 , 4 , 9 , 10 , 12 , 13 ?? (该序列实际上就是:3^0 ,3^1 , 3^0+3^1 , 3^2 , 3^0+3^2 , 3^1+3^2 , 3^0+3^1+3^2 ,? ) 请你求出这个序列的第 N 项的值(用 10 进制数表示) 。 例如,对于 k=3 , N = 100 ,正确答案应该是 981 。 【 输入文件】 输入文件 sequence.in 只有 l 行,为 2 个正整数,用一个空格隔开:k N ( k 、N 的含 义与上述的问题描述一致,且<= k<=15 , 10<=N<=1000) 。 【 输出文件】 输出文件 sequence.out 为计算结果,是一个正整数(在所有的测试数据中,结果均不超 过 2.1*10^9,整数前不要有空格和其他符号) 。 【 输入样例】 3 100 【 输出样例】 981

NOIP2007 年复赛试题
1. 奖学金 (scholar.pas/c/cpp) 【问题描述】 某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前 5 名学生发奖学金。 期末,每个学生都有 3 门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同, 再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学 排在前面, 这样,每个学生的排序是唯一确定的。 任务:先根据输入的 3 门课的成绩计算总分,然后按上述规则排序,最后按排名顺序输出前五名名学生的 学号和总分。注意,在前 5 名同学中,每个人的奖学金都不相同,因此,你必须严格按上述规则排序。例 如,在某个正确答案中,如果前两行的输出数据(每行输出两个数:学号、总分) 是: 7 279 5 279 这两行数据的含义是:总分最高的两个同学的学号依次是 7 号、5 号。这两名同学的总分都是 279 (总分等 于输入的语文、数学、英语三科成绩之和) ,但学号为 7 的学生语文成绩更高一些。如果你的前两名的输
20

出数据是: 5 279 7 279 则按输出错误处理,不能得分。 【输入】 输入文件 scholar.in 包含 n+1 行: 第 1 行为一个正整数 n,表示该校参加评选的学生人数。 第 2 到 n+1 行,每行有 3 个用空格隔开的数字,每个数字都在 O 到 100 之间 z 第 1 行的 3 个数 字依次表 示学号为 j-1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 l~n (恰好是输入 数据的行号减 1)。 【输出】 输出文件 scholar.out 共有 5 行,每行是两个用空格隔开的正整数,依次表示前 5 名学生的学 号和总分。 【输入输出样例 1】 scholar.in scholar.out 6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 6 265 4 264 3 258 2 244 1 237 【输入输出样例 2】 scholar. in scholar. out 8 80 89 89 88 98 78 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 8 265 2 264 6 264 1 258 5 258 【限制】 50%的数据满足:各学生的总成绩各不相同 100%的数据满足: 6<=n<=300
21

2.纪念品分组 group.pas/c/cpp) 【题目描述】 元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所 获得 的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念 品, 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品, 乐乐希望分组的数目最少。 你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。 【输入】输入文件 group.in 包含 n+2 行: 第 1 行包括一个整数 w,为每组纪念品价格之和的上眼= 第 2 行 为一个整数 n,表示购来的纪念品的总件数 G。 第 3-n+2 行每行包含一个正整数 Pi (5 <= Pi <= w3)w 表 示所对应纪念品的价格。 【输出】输出文件 group.out 仅→行,包含一个整数, ep 最少的分组数目合 【输入输出样例】 group.in group. out 100 9 90 20 20 30 50 60 70 80 90 6 【限制】 50%的数据满足: 1 <=n <= 15 100%的数据满足: 1 <= n <= 30000, 80 <= W <= 200 3. 守望者的逃离 (escape.pas/c/cpp) 【问题描述】 恶魔猎手尤迫安野心勃勃.他背叛了暗夜精灵,率深藏在海底的那加企图叛变:守望者在与 尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上。为了杀死守望者,尤迪安开始对这个荒岛施咒, 这座岛很快就会沉下去,到那时,刀上的所有人都会遇难:守望者的跑步速度,为 17m/s, 以这样的速度 是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术,可在 1s 内移动 60m,不过每次使用闪烁法术都会消耗 魔法值 10 点。守望者的魔法值恢复的速度为 4 点/s,只有处在原地休息状态时才能恢复。 现在已知守望者的魔法初值 M,他所在的初始位置与岛的出口之间的距离 S,岛沉没的时间 T。你的任务是 写一个程序帮助守望者计算如何在最短的时间内逃离荒岛,若不能逃出,则输出守望者在剩下的时间内能 走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。 距离的单位为米(m)。 【输入】 输入文件 escape.in 仅一行,包括空格隔开的三个非负整数 M,S,T。 【输出】 输出文件 escape.out 包含两行: 第 1 行为字符串"Yes"或"No" (区分大小写),即守望者是否 能逃离荒岛。 第 2 行包含一个整数,第一行为"Yes" (区分大小写)时表示守望着逃离荒岛的最短时间 第一行为"No" (区分大小写) 时表示守望者能走的最远距离。 【输入输出样例 1】 escape.in escape.out 39 200 4 No
22

197 【输入输出样例 2】 escape.in escape.out 36 255 10 Yes 6 【限制】 30%的数据满足: 1 <= T<= 10, 1 <=S<= 100 50%的数据满足: 1 <= T <= 1000, 1 <= S <= 10000 100%的数据满足: 1 <= T <= 300000, 0 <= M<=1000 1 <=S <= 10^8 4.Hanoi 双塔问题 hanoi.pas/c/cpp 【问题描述】给定 A,B,C 三根足够长的细柱,在 A 柱上放有 2n 个中间有空的圆盘,共有 n 个不同的尺寸, 每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的(下图为 n=3 的情形)。现要将 这些国盘移 到 C 柱上,在移动过程中可放在 B 柱上暂存。要求: (1)每次只能移动一个圆盘; (2) A、B、C 三根细 柱上的圆盘都要保持上小下大的顺序; 任务:设 An 为 2n 个圆盘完成上述任务所需的最少移动次数,对 于输入的 n,输出 An。 【输入】 输入文件 hanoi.in 为一个正整数 n,表示在 A 柱上放有 2n 个圆盘。 【输出】 输出文件 hanoi.out 仅一行,包含一个正整数,为完成上述任务所需的最少移动次数 An。 【输入输出样例 1】 hanoi.in hanoi.out 1 2 【输入输出样例 2】 hanoi.in hanoi.out 2 6 【限制】 对于 50%的数据, 1<=n<=25 对于 100% 数据, 1<=n<=200

NOIP2008 年复赛试题
1.ISBN 号码(isbn.pas/c/cpp) 【问题描述】每一本正式出版的图书都有一个 ISBN 号码与之对应,ISBN 码包括 9 位数字、1 位识别码和 3 位分隔符,其规定格式如“x-xxx-xxxxx-x” ,其中符号“-”是分隔符(键盘上的减号) ,最后一位是识别 码,例如 0-670-82162-4 就是一个标准的 ISBN 码。ISBN 码的首位数字表示书籍的出版语言,例如 0 代表 英语;第一个分隔符“-”之后的三位数字代表出版社,例如 670 代表维京出版社;第二个分隔之后的五 位数字代表该书在出版社的编号;最后一位为识别码。 识别码的计算方法如下:首位数字乘以 1 加上次位数字乘以 2??以此类推,用所得的结果 mod 11, 所得的余数即为识别码,如果余数为 10,则识别码为大写字母 X。例如 ISBN 号码 0-670-82162-4 中的识 别码 4 是这样得到的:对 067082162 这 9 个数字,从左至右,分别乘以 1,2,?,9,再求和,即 0×1+6 ×2+??+2×9=158,然后取 158 mod 11 的结果 4 作为识别码。 你的任务是编写程序判断输入的 ISBN 号码中识别码是否正确,如果正确,则仅输出“Right” ;如果 错误,则输出你认为是正确的 ISBN 号码。 【输入】输入文件 isbn.in 只有一行,是一个字符序列,表示一本书的 ISBN 号码(保证输入符合 ISBN 号 码的格式要求) 。 【输出】输出文件 isbn.out 共一行,假如输入的 ISBN 号码的识别码正确,那么输出“Right” ,否则,按 照规定的格式,输出正确的 ISBN 号码(包括分隔符“-”。 ) 【输入输出样例 1】 【输入输出样例 2】
23

isbn.in 0-670-82162-4

isbn.out Right

isbn.in 0-670-82162-0

isbn.out 0-670-82162-4

2.排座椅(seat.pas/c/cpp) 【问题描述】 上课的时候总有一些同学和前后左右的人交头接耳, 这是令小学班主任十分头疼的一件事情。 不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的 D 对同学上课时会 交头接耳。同学们在教室中坐成了 M 行 N 列,坐在第 i 行第 j 列的同学的位置是(i,j) ,为了方便同学 们进出,在教室中设置了 K 条横向的通道,L 条纵向的通道。于是,聪明的小雪想到了一个办法,或许可 以减少上课时学生交头接耳的问题:她打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条 通道隔开了两个会交头接耳的同学,那么他们就不会交头接耳了。请你帮忙给小雪编写一个程序,给出最 好的通道划分方案。在该方案下,上课时交头接耳的学生对数最少。 【输入】输入文件 seat.in 的第一行,有 5 各用空格隔开的整数,分别是 M,N,K,L,D(2<=N,M<=1000, 0<=K<M,0<=L<N,D<=2000) 。输入数据保证最优方案的唯一性。 接下来 D 行,每行有 4 个用空格隔开的整数,第 i 行的 4 个整数 Xi,Yi,Pi,Qi,表示坐在位置(Xi,Yi) 与(Pi,Qi)的两个同学会交头接耳(输入保证他们前后相邻或者左右相邻) 。 【输出】输出文件 seat.out 共两行。 第一行包含 K 个整数,a1a2??aK,表示第 a1 行和 a1+1 行之间、第 a2 行和第 a2+1 行之间、?、第 aK 行和第 aK+1 行之间要开辟通道,其中 ai< ai+1,每两个整数之间用空格隔开(行尾没有空格) 。 第二行包含 L 个整数,b1b2??bk,表示第 b1 列和 b1+1 列之间、第 b2 列和第 b2+1 列之间、?、第 bL 列和第 bL+1 列之间要开辟通道,其中 bi< bi+1,每两个整数之间用空格隔开(行尾没有空格) 。 【输入输出样例】 seat.in 4 5 1 2 3 4 2 4 3 2 3 3 3 2 5 2 4 4 3
4

seat.out 2 2 4

【输入输出样例解释】

*

* ※ ※ + +

2 1 1 道划分方案是唯一的最佳方案。 3.传球游戏 ball.pas/c/cpp) 2

3

4

5

上图中用符号*、※、+ 标出了 3 对会交头接耳的学生的位置,图中 3 条粗线的位置表示通道,图示的通

【问题描述】上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传 球游戏。游戏规则是这样的:n 个同学站成一个圆圈,其中的一个同学手里拿着一个球,当老师吹哨子时 开始传球,每个同学可以把球传给自己左右的两个同学中的一个(左右任意) ,当老师再次吹哨子时,传 球停止,此时,拿着球没传出去的那个同学就是败者,要给大家表演一个节目。 聪明的小蛮提出一个有趣的问题:有多少种不同的传球方法可以使得从小蛮手里开始传的球,传了 m 次以后,又回到小蛮手里。两种传球的方法被视作不同的方法,当且仅当这两种方法中,接到球的同学按
24

接球顺序组成的序列是不同的。比如有 3 个同学 1 号、2 号、3 号,并假设小蛮为 1 号,球传了 3 次回到 小蛮手里的方式有 1->2->3->1 和 1->3->2->1,共 2 种。 【输入】输入文件 ball.in 共一行,有两个用空格隔开的整数 n,m(3<=n<=30,1<=m<=30) 。 【输出】输出文件 ball.out 共一行,有一个整数,表示符合题意的方法数。 【输入输出样例】 ball.in 3 3 ball.out 2 +---+ / /| 高 +---+ | | | + |长 |/ 宽 +---+ 1 ..+---+---+ ./ / /| +---+---+ | | | | + | | |/. +---+---+.. 2 ?.+---+ ?/ /| ..+---+ | ./ /| + +---+ |/. | | +.. | |/? +---+?. 3

【限制】40%的数据满足:3<=n<=30,1<=m<=20; 100%的数据满足:3<=n<=30,1<=m<=30 4.立体图(drawing.pas/c/cpp) 【问题描述】小渊是个聪明的孩子,他经常会给周围的小朋友们讲些自己认为有趣的内容。 最近,他准备给小朋友们讲解立体图,请你帮他画出立体图。 小渊有一块面积为 m*n 的矩形区域,上面有 m*n 个边长为 1 的格子,每个格子上堆了 一些同样大小的吉姆(积木的长宽高都是 1) ,小渊想请你打印出这些格子的立体图。我们 定义每个积木为如下格式,并且不会做任何翻转旋转,只会严格以这一种形式摆放: ..+---+ ./ /| +---+ | | | + | |/| +---+ | | | + | |/. +---+.. 每个顶点用 1 个加号’+’表示,长用 3 个”-“表示,宽用 1 个”/” 表示,高用两个”|”表示。字符’+’‘-‘’/’‘|’的 ASCII 码分别为 43,45,47,124。字符’.’(ASCII 码 46)需要作为背景输出,即立体图 里的空白部分需要用’.’代替。立体图的画法如下面的规则:若两块积木 左右相邻,图示为右 2;若两块积木上下相邻,图示为左图:若两块积木前 后相邻,图示为右 3。 立体图中,定义位于第(m,1)的格子(即第 m 行第 1 列的格子)上面自底向

上的第一块积木(即最下面的一块积木)的左下角顶点为整张图最左下角的点。 【输入】输入文件 drawing.in 第一行有用空格隔开的两个整数 m 和 n,表示有 m*n 个格子 (1<=m,n<=50) 。 行第 j 列的格子上摞有多少个积木(1<=每个格子上的积木数<=100) 。

接下来的 m 行,是一个 m*n 的矩阵,每行有 n 个用空格隔开的整数,其中第 i 行第 j 列上的整数表示第 i 【输出】输出文件 drawing.out 中包含题目要求的立体图,是一个 K 行 L 列的字符矩阵,其中 K 和 L 表示 最少需要 K 行 L 列才能按规定输出立体图。 【输入输出样例】drawing.in 3 2 2 3 4 2 1 2 2 1 1 2 1 2 drawing.out

......+---+---+...+---+ ..+---+ / /|../ /| ./ /|-+---+ |.+---+ | +---+ |/ /| + | | + | | +---+ |/+---+ |/| | |/ /| +/ /|-+ | +---+---+ |/+---+ |/| + | | | +-| | + |/. | | |/ | |/| +.. +---+---+---+---+ |/... | | | | | +.... | | | | |/..... +---+---+---+---+......

25


相关文章:
1995-2008 历届NOIP试题及详解
1995-2008 历届NOIP试题及详解_学科竞赛_高中教育_教育专区。对历届(1995-2008)...复赛试题 第二届全国青少年信息学(计算机)奥林匹克分区联赛复赛试题 (高中组 ...
1995-2008全国初中数学联赛试题及答案
1995-2008全国初中数学联赛试题及答案_学科竞赛_初中教育_教育专区。1995-2008全国...竞赛决赛试题及答案 44 45 46 47 48 49 50 2006年全国初中数学联合竞赛决赛...
1995—2008复赛试题
1995-2008复赛试题及解析 25页 10财富值 1995-2008全国初中数学联赛... 78页...历届全国初中数学联赛试题... 2页 免费如要投诉违规内容,请到百度文库投诉中心;...
2008复赛试题
1995-2008复赛试题及解析... 25页 4下载券 2008全国应用物理知识竞... 12页...2008 年全国初中应用物理知识竞赛复赛试题 一、 (共 16 分)小明利用实验室的...
1995阅读真题及解析
公考片段阅读真题及解析 15页 免费 1995-2008复赛试题及解析... 25页 4下载...95 年阅读 Text1 11.[答案] D [解析] 本题考核的知识点是:句意题。 ...
1995-2008年高考试题语言连贯题汇
1995-2008年高考试题语言连贯题汇_高考_高中教育_教育专区。1995-2008年高考试题...A 【答案】C 评析:第 8 题,重点考的是关于语言连贯的问题。正确选项为 C。...
1995-2008全国初中数学联赛试题 (精华!每道题都有详解)
1995-2008全国初中数学联赛试题 (精华!每道题都有详解)还等什么,快来下载11995...数学竞赛和联赛好像不是一个地方组织的,全国数学竞赛比联赛题要简单一点,但决赛...
1995-2008年高考试题语言连贯题汇
1995-2008 年高考试题语言连贯题汇编 1995 年全国高考...一副石刻对联在门的两旁, 评析:这里,答案是 B。...发慢射决赛中以 566 环的成绩获得冠军,成 为中国...
2015~1995年育苗杯初复赛试题和答案
2015~1995年育苗杯初复赛试题答案_学科竞赛_小学教育_教育专区。2015~1995年...=(9.3 ) 4、计算 2015+2014-2013+2012-2011-2010+2009+2008-2007-2006+...
更多相关标签:
noip2016复赛试题 | 2016天原杯复赛试题 | noip提高组复赛试题 | 2016年迎春杯复赛试题 | 2015年迎春杯复赛试题 | noip复赛试题 | noip普及组复赛试题 | 信息学奥赛复赛试题 |