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