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.in0-670-82162-4isbn.outRight【输入输出样例2】isbn.in0-670-82162-0isbn.out0-670-82162-4【试题分析】基础字符串处理题，心细一点的基本都能得满分。
【参考程序】program isbn;constinp='isbn.in';oup='isbn.out';vari,j,k,ans:longint;s:string;ch:char;procedure flink;beginassign(input,inp);reset(input);assign(output,oup);rewrite(output);end;procedure fclose;beginclose(input);close(output);end;beginflink;readln(s);// 输入字符串j:=0;i:=1;ans:=0;while j<9 dobeginif s[i] in ['0'..'9'] then//如果是数字,那么累加到ans中,共9个数字begininc(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)]=chthen 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.in4 5 1 2 34 2 4 32 3 3 32 5 2 4seat.out22 4【试题分析】用的是赛前集训时提到的贪心，当时说某些题目用贪心可以得部分分，但是本题贪心可以得满分的。
当然本题的贪心需要预处理下，开2个一维数组，row[i]录如果在第i行加通道,可以分割多少对调皮学生,col[i]记录如果在第j列加通道,可以分割多少对调皮学生,最后贪心法输出分割学生最多的前K 行和前L列。
【参考程序】program seat;constinp='seat.in';oup='seat.out';varflag,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;beginassign(input,inp);reset(input);assign(output,oup);rewrite(output);end;procedure fclose;beginclose(input);close(output);end;function min(a,b:longint):longint;beginif a<b then exit(a); exit(b);end;procedure qsort(m,n:Longint);//快排vari,j,k,t:longint;begini:=m; j:=n; k:=tmp[(i+j) shr 1];repeatwhile tmp[i]>k do inc(i);while tmp[j]<k do dec(j);if i<=j thenbegint:=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;beginreadln(m,n,k,L,d);fillchar(row,sizeof(row),0);fillchar(col,sizeof(col),0);for i:= 1 to d do //统计在每行、每列添加通道可以分割的学生数beginreadln(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数组,准备排序beginif row[i]>0 thenbegininc(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) dobeginif row[i]>=flag then //如果该行能分割的人数不少于flag,说明此处可以添加通道 beginwrite(i);inc(j);if j<>k then write(' ');end;inc(i);end;writeln;//下面是求列通道,思想同上for i:= 1 to n dobeginif col[i]>0 thenbegininc(j);tmp[j]:=col[i];end;end;qsort(1,j);flag:=tmp[L];i:=1; j:=0;while (i<=m) and (j<L) dobeginif col[i]>=flag thenbeginwrite(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共一行，有一个整数，表示符合题意的方法数。