试题、程序及解题报告

1、2007年信息学分区联赛模拟赛试题解析 第一题 小白逛街 小白在一个由n条横街，m条纵街的地方逛街。现在他饿了，想去买小吃。已知小吃街在第n条横街上，且每个街区有ai家小吃店。小白站在这个地方的左上角，为了早点买到小吃，他只向下和向右走。 在这n*m的地方，从左上角，只向下和向右走到第n行的某一段的ai中任意一点，求有多少种不同的方案。同一家店不同路线 和 同一路线不同店均视为不同的方案。 white.in4 52101white.out262 1 0 1小白店店店店26= 2*1 + 1*4 + 0*10 + 1*20对于 30%数据, 0=n,m=10;ai=1对于100%数据, 0=n,

2、m=1000对于 100%数据，0=ai=1000数据规模对于 30%数据, 可以采用搜索2 1 0 11店店店店26= 2*1 + 1*4 + 0*10 + 1*20111111123434561010201535状态:f(i,j)表示到达第i条横街,第j条纵街的方案数.边界状态:f(1,1)=1f(1,i)=1 (1=i=n)f(i,1)=1 (1=i=bi。要求在这n个数对中选出k对，使得ai1+ai2+ai3+aik=m且bi1+bi2+bi3+bik=w，k为任意数，有几种方案。 food.in4 3 22 13 21 12 1food.out 3对于 30%数据, 0=n=10;

3、0=m,w=100对于100%数据, 0=n=50; 0=m,w=2,500对于 100%数据，0=ai,bi=100保证运算和输出不会超过maxlongint对于 30%数据, 可以采用搜索状态:f(i,j,k)表示利用前i个数对,首数和为j,尾数和为k的方案数.边界状态:动态规划f(1,i,j)=0 (im)or(jn)1 (i=m)and(j=n)ans=f(n,m,w)状态转移方程f(i,j,k)=f(i-1,j,k)f(i-1,j-ai,k-bi)(jai,kbi)ans=f(n,m,w)降维处理f(i,j)=maxf(i,j)f(i-ai,j-bi)(iai,jbi)ans=f(m

4、,w)第三题 小白的智商 小白是我们敬爱的数学课代表，所以智商是很高的，吃饱后的小白，智商更是不可估量。因此我们有难题都是找他解决的。他听说了我们的网球老师有欺负学生的倾向，对此他一直想为我们打抱不平。现在，他在无趣地逛街，但满脑子都在想对策。 我们的网球老师，假设他现在要测试我们的来回正反手，即一部分球扔向左边，另一部分球扔向右边，我们的任务就是把这些球尽量都打回去。但他现在有一筐网球，而且他扔球的速度很快，测试的同学来回跑也是很累的，所以到后面同学会因为太累而来不及跑到击球点把球打回去。他还要求，同学每次打球前要先回到中点。同学刚开始就站在中点。 现在用一个整数来表示老师扔球的位置，规定0

5、点为中点，老师不会把球扔在中点。第三题 小白的智商 每一个时刻老师都会扔出一个球，直到测试结束，共计n个时刻。同学的体力为m，每跑一个单位距离就会消耗体力1，同学的移动速度最快达到v，如果这个时刻的球打完没有体力回到中点，或不能及时跑到扔球点，那么同学就会选择在中点休息，每少打一个球同学的体力就会恢复k，现在询问这位同学会有多少个球打不到。 开始时刻是0，第一个球扔到是时刻1。只有正好在这个时刻整，且正好在扔球的位置，才能打到球。消耗体力只与移动距离有关。体力不会超过最初体力。最后一次打完球也要回到中点。 iq.in5 5 2 211-211iq.out2 数据规模对于 30%数据, 0=n=

6、100对于100%数据, 0=n=10,000对于 100%数据，0=ai,v,k=100;0=m=maxlongint算法模拟10 35 8 851515-122-2-1-3333533353329252119130153323211195135332734282216107335343027const maxn=10000;var f:text;n,m,v,k,num:longint; data:array 1.maxn of longint;begin init; main; print;cedure init;var i:longint;begin assign(f,iq

7、.in);reset(f);readln(f,n,m,v,k); for i:=1 to n do readln(f,datai);close(f);end;procedure print;begin assign(f,iq.out);rewrite(f);writeln(f,num); close(f);end;procedure main;var i,m1:longint;begin num:=0;m1:=m; if m=abs(datai)*2+abs(datai-1)and (v=abs(datai-1)+abs(datai) then m:=m-abs(datai-1)-abs(datai) else begin inc(num);datai:=0; if m+km1 then m:=m+k else m:=m1; end; end;end;第四题 数字游戏 不知不觉小白已经到家了。他打开自己的草稿本，开始了自己新的研究。 按顺序给出n个数的数列，现在需要从中求出连续几个数的和的最大，连续的数的个数要在s和t之间。 game.in5 2 31-23-45game.out4数据范围对于30%数据,1=s=t=n=100对于100%数,1=s=t=n=100,000对于 100%数据，ai=10000动态规划状态:f(i)表示i-n段的最优值边界