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

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

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

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列的格子）上面自底向上的第一块积木（即最下面的一块积木）的左下角顶点为整张图最左下角的点。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库NOIP2008普及组复赛试题与解题报告(2)在线全文阅读。