四川省选day2

1、noi20092009四川省选拔赛试题与解题报告四川省选拔赛试题与解题报告第二试试题与解题报告第一题最长距离【问题描述】windy有一块矩形土地，被分为n*m块 1*1的小格子。有的格子含有障碍物。如果从格子a 可以走到格子b，那么两个格子的距离就为两个格子中心的欧几里德距离。如果从格子a 不可以走到格子b，就没有距离。如果格子 x 和格子 y 有公共边，并且x 和 y 均不含有障碍物，就可以从x 走到 y。如果 windy可以移走t 块障碍物，求所有格子间的最大距离。保证移走 t 块障碍物以后，至少有一个格子不含有障碍物。【输入格式】输入文件 maxlength.in第一行包含三个整数：第一

2、行包含三个整数：n n ，m ，t。接下来有 n 行，每行一个长度为m 的字符串，的字符串， 000 表示空格子，表示空格子，表示空格子，111 表示该格子含有障表示该格子含有障碍物。【输出格式】输出文件 maxlength.out包含一个浮点数，保留包含一个浮点数，保留6 6位小数。【输入样例一】3 3 0001001110【输出样例一】1.414214【输入样例二】4 3 0001001011000【输出样例二】3.605551【输入样例三】3 3 1001001001【输出样例三】2.828427【数据规模和约定】20%20% 的数据，满足的数据，满足1 n,mn,m 30； 0t 0

3、。40%40% 的数据，满足的数据，满足1 n,mn,m 30； 0 t 2 。100%100% 的数据，满足的数据，满足1 n,m30； 0 t 30。第二题：粉刷匠【问题描述】windy有 n条木板需要被粉刷。每条木板被分为m个格子。每个格子要被刷成红色或蓝色。windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉刷一次。如果 windy只能粉刷t 次，他最多能正确粉刷多少格子？一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。【输入格式】输入文件 paint.in第一行包含三个整数：第一行包含三个整数：n n ，m ，t。接下来有 n 行，每行一个

4、长度为m 的字符串，的字符串， 000 表示红色，表示红色，表示红色， 111 表示蓝色。表示蓝色。【输出格式】输出文件 paint.out包含一个整数，最多能正确粉刷的格子数。【输入样例】3 6 3111111000000001100【输出样例】16【数据规模和约定】30%30% 的数据，满足的数据，满足1 n,m 10； 0 t 100。100%100% 的数据，满足的数据，满足1 n,mn,m 50 ； 0 t 2500。第三题：迷路【问题描述】windy在有向图中迷路了。该有向图有n 个节点个节点， ， windy从节点0 出发出发， 他必须恰好在t 时刻到达节点n-1n-1。 。现在

5、给出该有向图，你能告诉windy总共有多少种不同的路径吗？注意：注意： windywindy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。【输入格式】输入文件 road.in第一行包含两个整数：第一行包含两个整数：n n ，t。接下来有n 行，每行一个长度为n的字符串。第 i 行第 j 列为列为 000 表示从节点表示从节点i 到节点 j 没有边。为11 到到99 表示从节点表示从节点i 到节点 j 需要耗费的时间。【输出格式】输出文件 road.out包含一个整数包含一个整数， ，可能的路径数可能的路径数， ，这个数可能很大这个数可能很大，只需输出这个数除以除以 20092009

6、2009的余数。的余数。【输入样例一】2 21100【输出样例一】1【样例解释一】0-0-1【输入样例二】5 301204507105478051202412345【输出样例二】852【数据规模和约定】30%30% 的数据，满足的数据，满足2 n 5 ； 1t 30。100%100% 的数据，满足的数据，满足2 n 10； 1 t 1000000000。【解题报告】第一题第一题: :最长距离分析分析： ：此题如果总想要枚举移走哪几块障碍的话此题如果总想要枚举移走哪几块障碍的话，是不可能 ac 的。但只要稍稍换一个角度角度， ，就豁然开朗就豁然开朗。 。直接算出某两格之间最短要经过几个障碍物直接

7、算出某两格之间最短要经过几个障碍物，然后枚举任意两格然后枚举任意两格，如果经过障碍物数小于等于总个数说明这两格可行。取所有可行里的最优即可。最短路可以经过障碍物数小于等于总个数说明这两格可行。取所有可行里的最优即可。最短路可以用用spfaspfa ，对这道题的特殊图对这道题的特殊图，也可以用双重bfsbfs ：即对不过障碍的情况bfsbfs ，再对过障碍的情况 bfsbfs ，交替进行直到遍历整个图交替进行直到遍历整个图。 。而我的程序也用的这种思想而我的程序也用的这种思想， ，但对不过障碍的情况用的是 dfsdfs ，这样写起来方便一些。，这样写起来方便一些。参考程序：programmaxl

8、ength;constdx:array1.4oflongint=(0,0,-1,1);dy:array1.4oflongint=(1,-1,0,0);varmap:array1.30,1.30ofchar;d:array1.30,1.30oflongint;duix,duiy:array1.900oflongint;best,i,j,n,m,t,head,tail:longint;ans:extended;procedureinit;beginreadln(n,m,t);fori:=1to n do beginforj:=1to m do read(mapi,j);readln;end;end

9、;proceduredfs(x,y:longint);vari,x1,y1:longint;beginfori:=1to 4 do beginx1:=x+dxi;y1:=y+dyi;if(x1n)or(y1m)or(x1=0)or(y1=0)thencontinue;if(mapx1,y1=0)and(dx1,y1=-1)thenbegininc(tail);duixtail:=x1;duiytail:=y1;dx1,y1:=dx,y;dfs(x1,y1);end;end;end;procedurebfs(x,y:longint);vari,x1,y1,x2,y2,temp:longint;b

10、eginfillchar(d,sizeof(d),$ff);if mapx,y=1thendx,y:=1else dx,y:=0;head:=0;tail:=1;duix1:=x;duiy1:=y;dfs(x,y);repeatinc(head);x1:=duixhead;y1:=duiyhead;/dfs(x1,y1);fori:=1to 4 do beginx2:=x1+dxi;y2:=y1+dyi;if(x2n)or(y2m)or(x2=0)or(y2=0)thencontinue;if(dx2,y2=-1)thenbegininc(tail);duixtail:=x2;duiytail

11、:=y2;dx2,y2:=dx1,y1+1;dfs(x2,y2);end;end;untilhead=tail;forx1:=1to n dofory1:=1to m doif (dx1,y1bestthenbest:=temp;end;end;beginassign(input,maxlength.in);reset(input);assign(output,maxlength.out);rewrite(output);init;best:=0;fori:=1to n doforj:=1to m dobfs(i,j);ans:=best;ans:=sqrt(ans);writeln(ans:

12、0:6);close(input);close(output);end.第二题：粉刷匠此题阶段性非常明显。显然每一层怎么刷的次数定了之后，又不再与其他层有关系了此题阶段性非常明显。显然每一层怎么刷的次数定了之后，又不再与其他层有关系了。而每一层的前几个刷了几次而每一层的前几个刷了几次， ，也和这一层的后面那些没有关系了也和这一层的后面那些没有关系了。因此可以用两次动态规划解决解决。 。对每一层对每一层， ，fi,jfi,j代表前代表前 i 个格子刷j 次最多可以刷的格子数次最多可以刷的格子数。 。对整个图对整个图， ，gi,jgi,j代表代表代表前 前i 行刷 j 次最多可以刷的格子数次最多可

13、以刷的格子数。 。每一行上是一个区间的动态规划问题每一行上是一个区间的动态规划问题，而整个图则是个而整个图则是个0101背包问题。参考程序：programpaint;varmap,sum1,sum2:array1.50,0.50oflongint;num:array1.50oflongint;dp,g:array0.50,0.50oflongint;f:array0.50,0.2500oflongint;n,m,t,i,j:longint;z,last:char;procedureinit;beginreadln(n,m,t);fori:=1to n do beginnumi:=0;last:

14、=;forj:=1to m do beginread(z);if zlastthenbegininc(numi);mapi,numi:=1;end else inc(mapi,numi);last:=z;end;forj:=1to numido beginsum1i,j:=sum1i,j-1;sum2i,j:=sum2i,j-1;if j and 1=1theninc(sum1i,j,mapi,j)else inc(sum2i,j,mapi,j);end;readln;end;end;proceduredp1(k:longint);vari,j,l,temp:longint;beginfill

15、char(dp,sizeof(dp),0);fori:=1to numkdo beginforj:=1to numkdo begindpj,i:=dpj-1,i;forl:=1to j do begintemp:=sum1k,j-sum1k,l-1;if sum2k,j-sum2k,l-1tempthentemp:=sum2k,j-sum2k,l-1;temp:=temp+dpl-1,i-1;if tempdpj,ithendpj,i:=temp;end;end;gk,i:=dpnumk,i;end;end;proceduredp2;vari,j,l,temp:longint;beginfil

16、lchar(f,sizeof(f),0);fori:=1to n doforj:=1to t do beginfi,j:=fi-1,j;forl:=1to numido if j=lthenbegintemp:=fi-1,j-l+gi,l;if tempfi,jthenfi,j:=temp;end;end;end;beginassign(input,paint.in);reset(input);assign(output,paint.out);rewrite(output);init;fillchar(g,sizeof(g),0);fori:=1to n do dp1(i);dp2;write

17、ln(fn,t);close(input);close(output);end.第三题：迷路这道题是矩阵乘法的经典应用这道题是矩阵乘法的经典应用。 。 我们考虑一个简化版我们考虑一个简化版， ，点与点之间只能有连和不连两种情况，连的话距离为情况，连的话距离为1 1。令 fk,i,jfk,i,j代表从代表从 i 到 j 走 k 步的方案数，那么一定有f2k,i,j:=f2k,i,j:= (fk,i,p*fk,p,j)(0(0 p n-1).因此整个矩阵因此整个矩阵(实际矩阵中没有k 这一维这一维) )就可以用一个矩阵乘法来完成就可以用一个矩阵乘法来完成。 。 用类似二分快速幂的方法可以做到o(l

18、ogln3)o(logln3) 的时间复杂度。的时间复杂度。但这道题并不那么但这道题并不那么“裸”，因为题中点间距离可能为，因为题中点间距离可能为1,91,91,9。注意到距离并不大，所以。注意到距离并不大，所以可以把一个点拆成可以把一个点拆成9 9个“分点分点” ”， 然后这然后这9 9个“分点分点”构成一条链构成一条链， ， 相邻的相邻的“ “分点分点”距离为距离为1 1。如果从 i 到 j 有一条长k 的路径的路径， ， 那么就从i 的最后一个的最后一个“ “分点分点” 连一条长连一条长11的边到 j 的倒数第 k 个“分点分点” ”。最后统计第最后统计第0 0个点的最后一个分点到第n-1n-1 个点的最后一个分点的方案数个点的最后一个分点的方案数即可即可。 。最终时间复杂度o(logln3o(logln3 ） ） ，要乘上一个要乘上一个 939393的常数的常数的常数。 。不过还是在可以接受的范围的不过还是在可以接受的范围的。 。参考程序：$m100000000programroad;typejz=array1.90,1.90oflongint;varans,be:jz;i,j,n,t,x,size:longint;z:char;procedureinit;beginreadln(n,t);fori:=0to n-1do begin