tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 学科竞赛 >>

NOIP2008普及组复赛试题与解题报告


NOIP 2008 普及组解题报告
一、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】 isbn.in 0-670-82162-4

isbn.out Right 【输入输出样例 2】 isbn.in

0-670-82162-0

isbn.out 0-670-82162-4

【试题分析】 基础字符串处理题,心细一点的基本都能得满分。

【参考程序】 program isbn; const inp='isbn.in'; oup='isbn.out';

var i,j,k,ans:longint; s:string; ch:char; procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end; procedure fclose; begin close(input); close(output); end;

begin flink; readln(s);// 输入字符串 j:=0;

i:=1; ans:=0; while j<9 do begin if s[i] in ['0'..'9'] then//如果是数字,那么累加到 ans 中,共 9 个数字 begin inc(j); inc(ans,(ord(s[i])-ord('0'))*j); end; inc(i); end; ans:=ans mod 11;计算识别码 if ans=10 then ch:='X' else ch:=chr(ord('0')+ans);//把识别码转换成字符,方便输出 if s[length(s)]=ch then write('Right') else write(copy(s,1,12)+ch);//输出正确的识别码 fclose; end.

二、排座椅(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

seat.out 2 2 4

【试题分析】 用的是赛前集训时提到的贪心,当时说某些题目用贪心可以得部分分,但是本题贪心可以得满分的。 当然本题的贪心需要预处理下,开 2 个一维数组,row[i]录如果在第 i 行加通道,可以分割多少对调皮 学生,col[i]记录如果在第 j 列加通道,可以分割多少对调皮学生,最后贪心法输出分割学生最多的前 K 行和前 L 列。

【参考程序】 program seat; const inp='seat.in'; oup='seat.out'; var flag,m,n,k,l,d,i,j,x,y,x1,y1:longint; tmp,col,row:array[1..1000] of longint;

s,s1:ansistring; procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end; procedure fclose; begin close(input); close(output); end; function min(a,b:longint):longint; begin if a<b then exit(a); exit(b); end; procedure qsort(m,n:Longint);//快排 var i,j,k,t:longint; begin i:=m; j:=n; k:=tmp[(i+j) shr 1]; repeat while tmp[i]>k do inc(i); while tmp[j]<k do dec(j); if i<=j then begin t:=tmp[i]; tmp[i]:=tmp[j]; tmp[j]:=t; inc(I); dec(J); end; until i>j; if m<j then qsort(m,j); if I<n then qsort(i,n); end; begin

flink; readln(m,n,k,L,d); fillchar(row,sizeof(row),0); fillchar(col,sizeof(col),0); for i:= 1 to d do //统计在每行、每列添加通道可以分割的学生数 begin readln(x,y,x1,y1); if (x=x1) then inc(col[min(y,y1)]) else inc(row[min(x,x1)]); end; j:=0; for i:= 1 to m do //把能没个行通道分割的学生数加入 tmp 数组,准备排序 begin if row[i]>0 then begin inc(j); tmp[j]:=row[i]; end; end; qsort(1,j);//对 tmp 数组排序 flag:=tmp[k];//flag 为前 K 项的最小值 i:=1; j:=0; while (i<=n) and (j<k) do begin if row[i]>=flag then //如果该行能分割的人数不少于 flag,说明此处可以添加通道 begin write(i); inc(j); if j<>k then write(' '); end; inc(i); end; writeln; //下面是求列通道,思想同上

j:=0; for i:= 1 to n do begin if col[i]>0 then begin inc(j); tmp[j]:=col[i]; end; end; qsort(1,j); flag:=tmp[L]; i:=1; j:=0; while (i<=m) and (j<L) do begin if col[i]>=flag then begin write(i); inc(j); if j<>L then write(' '); end; inc(i); end; fclose; end.

三、传球游戏(seat.pas/c/cpp)

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

【试题分析】 直接 dp,似乎说递推更确切点。f(i,k)表示经过 k 次传到编号为 i 的人手中的方案数。那么可以推 出下面的方程: f(i,k)=f(i-1,k-1)+f(i+1,k-1) (i=1 或 n 时, 需单独处理) 。 边界条件: f(1,0)=1。 结果在 f(1,m)中。

【参考程序】 program ball; const inp='ball.in'; oup='ball.out'; var i,j,k,n,m:longint; f:array[0..30,0..30] of longint; procedure flink; begin assign(input,inp); reset(input); assign(output,oup);

rewrite(output); end; procedure fclose; begin close(input); close(output); end;

begin flink; readln(n,m); fillchar(f,sizeof(f),0); f[1,0]:=1; for k:=1 to m do//注意此处 2 个循环的次序 begin f[1,k]:=f[2,k-1]+f[n,k-1]; for i:= 2 to n-1 do f[i,k]:=f[i-1,k-1]+f[i+1,k-1]; f[n,k]:=f[n-1,k-1]+f[1,k-1]; end; write(f[1,m]); fclose; end. 四、立体图(drawing.pas/c/cpp)

【问题描述】 小渊是个聪明的孩子,他经常会给周围的小朋友们讲些自己认为有趣的内容。最近,他准备给小朋友 们讲解立体图,请你帮他画出立体图。 小渊有一块面积为 m*n 的矩形区域,上面有 m*n 个边长为 1 的格子,每个格子上堆了一些同样大小的 积木(积木的长宽高都是 1) ,小渊想请你打印出这些格子的立体图。我们定义每个积木为如下格式,并且 不会做任何翻转旋转,只会严格以这一种形式摆放: +---+ / /| 高

+---+ | | | +

|

|/ 宽

+---+ 长 每个顶点用 1 个加号’+’表示,长用 3 个”-“表示,宽用 1 个”/”表示,高用两个”|”表示。字 符‘+’‘-’ ‘/’ ‘|’的 ASCII 码分别为 43,45,47,124。字符’.’(ASCII 码 46)需要作为背景输出, 即立体图里的空白部分需要用’.’代替。立体图的画法如下面的规则: 若两块积木左右相邻,图示为: ..+---+---+ ./ / /|

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

+---+---+.. 若两块积木上下相邻,图示为: ..+---+ ./ /|

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

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

+---+.. 若两块积木前后相邻,图示为: ?.+---+ ?/ /|

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

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

+---+?. 立体图中,定义位于第(m,1)的格子(即第 m 行第 1 列的格子)上面自底向上的第一块积木(即最下 面的一块积木)的左下角顶点为整张图最左下角的点。

【输入】 输入文件 drawing.in 第一行有用空格隔开的两个整数 m 和 n,表示有 m*n 个格子(1<=m,n<=50) 。 接下来的 m 行,是一个 m*n 的矩阵,每行有 n 个用空格隔开的整数,其中第 i 行第 j 列上的整数表示 第 i 行第 j 列的格子上摞有多少个积木(1<=每个格子上的积木数<=100) 。

【输出】 输出文件 drawing.out 中包含题目要求的立体图,是一个 K 行 L 列的字符矩阵,其中 K 和 L 表示最少 需要 K 行 L 列才能按规定输出立体图。

【输入输出样例】 drawing.in 3 4 2 2 1 2 2 2 1 1 3 2 1 2

drawing.out ......+---+---+...+---+ ..+---+ ./ / /|../ /|

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

+---+ |/ | |

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

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

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

+---+---+---+---+......

【试题分析】 Pku 原题,编号 2330,算不上难题,但是比较麻烦,细心点就 ok 了。 先计算好画布的大小,再写一个根据左下角坐标绘制一个单位立方体的子程序。然后遵循下面法则,

不停绘制若干个立方体。 (此处能体现出分割程序的伟大) 。 因为要不停的覆盖,所以要遵循“视觉法则”: 1、先绘里层再绘外层。 2、先绘底层再绘上层。 3、先回左边再绘右边。

【参考程序】 program drawing; const inp='drawing.in'; oup='drawing.out'; var m,n,i,j,k,x,y,h,tmp,maxx,maxy:longint; map:array[1..1000,1..1000] of char;//画布 a:array[1..50,1..50] of integer;//记录输入的矩阵 procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end; procedure fclose; begin close(input); close(output); end; procedure print;//输出画布 var i,j:longint; begin for i:= 1 to maxx do begin for j:= 1 to maxy do write(map[i,j]);

if i<>maxx then writeln; end; end; procedure draw(x,y:longint);//在画布(map 数组)上绘制左下角坐标为(x,y)的一个单位立方 体 begin map[x,y]:='+';map[x,y+1]:='-'; map[x,y+2]:='-';map[x,y+3]:='-';map[x,y+4]:='+'; dec(x); map[x,y]:='|';map[x,y+1]:=' ';map[x,y+4]:='|'; map[x,y+5]:='/'; dec(x); map[x,y]:='|';map[x,y+1]:=' ';map[x,y+4]:='|'; map[x,y+5]:=' ';map[x,y+6]:='+'; dec(x); map[x,y]:='+';map[x,y+1]:='-'; map[x,y+2]:='-';map[x,y+3]:='-';map[x,y+4]:='+'; map[x,y+5]:=' ';map[x,y+6]:='|'; dec(x); inc(y); map[x,y]:='/';map[x,y+1]:=' ';map[x,y+4]:='/'; map[x,y+5]:='|'; dec(x);inc(y); map[x,y]:='+';map[x,y+1]:='-'; map[x,y+2]:='-';map[x,y+3]:='-';map[x,y+4]:='+'; '; map[x,y+2]:=' ';map[x,y+3]:=' '; map[x,y+2]:=' ';map[x,y+3]:=' '; map[x,y+2]:=' ';map[x,y+3]:='

end;

begin flink; for i:= 1 to 1000 do for j:= 1 to 1000 do map[i,j]:='.'; //初始化画布

readln(m,n); //计算画布大小 maxx * maxy maxy:=n*4+1+m*2; maxx:=0; for i:= 1 to m do begin tmp:=0; for j:= 1 to n do begin read(a[i,j]); if a[i,j]>tmp then tmp:=a[i,j]; end; tmp:=tmp*3+3+(m-i)*2; if tmp >maxx then maxx:=tmp; readln; end; //开始往画布上绘图 for i:= 1 to m do for j:= 1 to n do begin x:=maxx-(m-i)*2;//第 i 层第 j 列最下方立方体左下角点的位置(x,y) y:=(m-i)*2+(j-1)*4+1; for k:= 1 to a[i,j] do draw(x-(k-1)*3,y);//绘制每层的若干个一个单位立方体 end; print;//输出画布 fclose; end.



推荐相关:

NOIP2008提高组前三题解题报告

NOIP2008 提高组前三题解题报告 [日期:2008-11-18] 来源: 作者:张恩权 [...NOIP2008_复赛试卷_提高... 6页 免费 NOIP2008普及组 复赛解题... 11页...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com