2008noip普及组复赛题

全国信息学奥林匹克联赛（NOIP2008）复赛

普及组

一.题目概览
中文题目名称 ISBN号码 排座椅 传球游戏 立体图
英文题目名称 isbn seat ball drawing
可执行文件名 isbn seat ball drawing
输入文件名 isbn.in seat.in ball.in drawing.in
输出文件名 isbn.out seat.out ball.out drawing.out
每个测试点时限 1秒 1秒 1秒 1秒
测试点数目 10 10 10 10
每个测试点分值 10 10 10 10
比较方式 全文比较 全文比较 全文比较 全文比较
题目类型 传统 传统 传统 传统

二.提交源程序文件名
对于pascal语言 isbn.pas seat.pas ball.pas drawing.pas
对于C语言 isbn.c seat.c ball.c drawing.c
对于C++语言 isbn.cpp seat.cpp ball.cpp drawing.cpp

三.编译命令（不包含任何优化开关）
对于pascal语言 fpc isbn.pas fpc seat.pas fpc ball.pas fpc drawing.pas
对于C语言 gcc –o isbn
isbn.c gcc –o seat
seat.c gcc –o ball
ball.c gcc –o drawing
drawing.c
对于C++语言 g++ –o isbn
isbn.cpp g++ –o seat
seat.cpp g++ –o ball
ball.cpp g++ –o
drawing
drawing.cpp

四.运行内存限制
运行内存上限 50M 50M 50M 50M

注意事项：
1、文件名（程序名和输入输出文件名）必须使用小写。
2、C/C++中函数main（）的返回值类型必须是int，程序正常结束时的返回值必须是0。
3、全国统一评测时采用的机器配置为：CPU 1.9GHz， 内存512M， 上述时限以此配置为准。
各省在自测时可根据具体配置调整时限。

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】
isbn.in isbn.out
0-670-82162-4 Right

【输入输出样例2】
isbn.in isbn.out
0-670-82162-0 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接下来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 seat.out
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4 2
2 4
【输入输出样例解释】

* *

※

※ + +

1 2 3 4 5

上图中用符号*、※、+ 标出了3对会交头接耳的学生的位置，图中3条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。

3.传球游戏
（ball.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 ball.out
3 3 2

【限制】
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）需要作为背景输出，即立体图里的空白部分需要用’.’代替。立体图的画法如下面的规则：
若两块积木左右相邻，图示为：
..+---+---+
./ / /|
+---+---+ |
| | | +
| | |/.
+---+---+..
若两块积木上下相邻，图示为：
..+---+
./ /|
+---+ |
| | +
| |/|
+---+ |
| | +
| |/.
+---+..
若两块积木前后相邻，图示为：
….+---+
…/ /|
..+---+ |
./ /| +
+---+ |/.
| | +..
| |/…
+---+….
立体图中，定义位于第(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 drawing.out
3 4
2 2 1 2
2 2 1 1
3 2 1 2 ......+---+---+...+---+
..+---+ / /|../ /|
./ /|-+---+ |.+---+ |
+---+ |/ /| +-| | +
| | +---+ |/+---+ |/|
| |/ /| +/ /|-+ |
+---+---+ |/+---+ |/| +
| | | +-| | + |/.
| | |/ | |/| +..
+---+---+---+---+ |/...
| | | | | +....
| | | | |/.....
+---+---+---+---+......

NOIP2008解题报告

一、ISBN号码

基础字符串处理题，心细一点的基本都能得满分。

参考程序：

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.

二、排座椅

用的是赛前集训时提到的贪心，当时说某些题目用贪心可以得部分分，但是本题贪心可以得满分的。

当然本题的贪心需要预处理下，开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
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]
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
if I
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
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
begin

if col[i]>=flag then

begin

write(i);

inc(j);

if j<>L then write(' ');

end;

inc(i);

end;

fclose;

end.

三、传球游戏

直接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.

四、立体图

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+2]:=' ';map[x,y+3]:=' ';map[x,y+4]:='|';

map[x,y+5]:='/';

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

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+2]:=' ';map[x,y+3]:=' ';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]:='+';

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.