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普及组复赛试题与解题报告.doc

NOIP 2008 普及组解题报告一、ISBN 号码(isbn.pas/c/cp


NOIP2008普及组复赛试题.doc

NOIP2008普及组试题 7页 免费喜欢此文档的还喜欢 NOIP2010普及组复赛试题 7页 免费 NOIP2008普及组复赛试题 6页 1下载券 NOIP2008普及组复赛解题... 11页 免费...


noip2008普及组复赛试题(附题解).doc

全国信息学奥林匹克联赛(NOIP2008)复赛 普及组 全国信息学奥林匹克联赛(NOIP...NOIP2008普及组 复赛解题... 11页 免费 NOIP2010普及组复赛试题 8页 免费 ...


2008年NOIP普及组解题报告.pdf

2008NOIP 普及组解题报告 王祺磊 (本份解题报告以 C++为参考程序) 一、...NOIP2007普及组解题报告 12页 免费 NOIP2009普及组复赛试题... 3页 免费 ...


08普及组复赛+解题报告.pdf

08普及组复赛+解题报告 - 全国信息学奥林匹克联赛(NOIP2008)复赛 普


2008noip提高组复赛题解.doc

2008noip提高组复赛题解_学科竞赛_高中教育_教育专区。NOIP2008 提高组解题报告...实际上,对于如此普及组难度的水题,即使实力一般,也可能拿到不错的成绩。 希望 ...


noip2017普及组复赛解题报告.pdf

noip2015普及组解题报告 14页 1下载券 NOIP08普及组解题报告 6页 免费 喜欢此文档的还喜欢 NOIP2017复赛普及组试题 9页 1下载券 NOIp2017普及组解题报告.....


NOIP2008提高组复赛试题及题解.doc

NOIP2008普及组复赛试题... 16页 免费 NOIP2008复赛提高组试题 6页 免费 ...NOIP2008提高组解题报告 13页 1下载券 NOIP2008提高组前三题解... 13页 免费...


2009NOIP普及组复赛解题报告.doc

2009NOIP普及组复赛解题报告 - 2009 年答案 多项式输出 问题转述: 给出一个一元多项式各项的次数系数,按照规定的格式要求输出该多项式。 分析: 普及组的水题。...


NOIP2007普及组解题报告.doc

NOIP2007普及组解题报告_IT/计算机_专业资料。NOIP2008普及组复赛试题与解题报告 NOIP 2007 普及组解题报告 1、 奖学金 (scholar.pas/c/cpp) 、 【问题描述】 ...


NOIP2008普及组复赛试题(附题解).doc

NOIP2008普及组复赛试题(附题解)_其它考试_资格考试...2014年建筑幕墙建筑装饰行业分析报告 104份文档 2014...3页 免费 NOIP2004普及组复赛解题... 8页 免费...


NOIP2008普及组复赛试题(附题解).doc

NOIP2008普及组复赛试题(附题解)NOIP2008普及组复赛试题(附题解)隐藏>> 全国信息学奥林匹克联赛 NOIP2008 复赛 普及组一.题目概览中文题目名称 英文题目名称 可执...


NOIP2009普及组复赛试题解题报告.doc

NOIP2009普及组复赛试题解题报告_IT/计算机_专业资料。NOIP2009普及组复赛试题解题报告 NOIP2009 普及组复赛试题解题报告许建峰 1,多项式输出 本题只是一个基本知识点...


NOIP2017普及组复赛-解题报告.pdf

衢州市兴华中学 NOIP2017 普及组复赛 By 冯明浩 NOIP2017 普及组复赛-解题报告 衢州市兴华中学 By 冯明浩 Score 题目大意 考察算法 算法一 算法二 成绩给出三个...


NOIP2008普及组复赛试题.pdf

NOIP2008普及组复赛试题 - 全国信息学奥林匹克联赛(NOIP2008)复


NOIP2013普及组复赛试题+解题报告.pdf

NOIp2013 普及组 解题报告 By 绍兴文理学院附中 任轩笛 NOIp2013 普及组 解题报告 By 绍兴文理学院附中 任轩笛 表达式求值(expr.pas/c/cpp) Time Limit:1000...


NOIP2008普及组(复赛).doc

NOIP2008普及组(复赛) - 全国信息学奥林匹克联赛(NOIP2008)复赛 普及组 全国信息学奥林匹克联赛(NOIP2008)复赛 普及组 一.题目概览 中文题目名称 英文题目名称...


NOIP2015普及组复赛解题报告.doc

NOIP2015普及组复赛解题报告_学科竞赛_初中教育_教育专区。NOIP2015普及组复赛解题报告 NOIP2015 普及组解题报告南京师范大学附属中学树人学校 CT 1. 金币(coin.cpp/...


NOIP08普及组解题报告.doc

NOIP08普及组解题报告 - NOIP2008 普及组解题报告 By sx349 一、 ISBN 号码 (isbn.pas/c/cpp) 【问题描述】 每一本正式出版的图书都有一个 ISBN ...


08年信息学竞赛解题报告.doc

08年信息学竞赛解题报告 - NOIP2008 普及组复赛 解题报告 ] NOIP2008 解题报告 张恩权 一、ISBN 号码 基础字符串处理题,心细一点的基本都能得满分。 参考程序...

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