集训队作业9801解题报告

1、POI V Stage1 Problem1Paers Studio画家的解题张家琳复旦大学附属中学这道题涉及到正方形的移动问题，但由于正方形的边长最多可达 2100，即使线性的算法也出不了解。从这点上看，此题似乎无从下手。但题目本身不仅明确提示 正方形的边长一定是 2 的幂次，而且正方形上的孔又是按照“四分的方法”递归确定的，这就启示以 100（而不是 2100）作为时空复杂度的考虑，由此很容易想到，这道题一定是用递推或者递归的方法求解的。经过仔细观察，可以发现如下的规律：首先定义f 数组表示：fn,1表示将正方形向上移x 格向右移y 格所共同覆盖的格子数;fn,2表示将正方形向上移x 格向2

2、n-y 格所共同覆盖的格子数；fn,3表示将正方形向下移 2n-x 格向右移 y 格所共同覆盖的格子数；fn,4表示将正方形向下移 2n-x 格向2n-y 格所共同覆盖的格子数。可以分别用fn-1,i来表示fn,j：具体来说，将一个 2n*2n 的正方形分成四个 2(n-1)*2(n-1)的正方形（如下图），其中两者 的部份被分成若干块小长方形，例如：其中 1 号长方形可以看作右下角的正方形向上移x 格向右移 y 格，而 2 号长方形可以看作右上角的正方形向下移 2n-x 格向2n-y 格。利用这样的方法可以写出递推的方程。注意：对x y 与 2(n-1)的大小要进行。具体如下：1x,y2(n

3、-1)的情况fn,1=3*fn-1,1+fn-1,2+fn-1,3+fn-1,4; fn,2=fn-1,2;fn,3=fn-1,3;fn,4=fn-1,4;左图仅表示求fn,1的情况。2x=2(n-1) fn,1=fn-1,1+fn-1,2; fn,2=0;fn,3=3*fn-1,3+fn-1,1+fn-1,4; fn,4=fn-1,4+fn-1,23x=2(n-1),y=2(n-1) fn,1=fn-1,1;fn,2=fn-1,2;fn,3=fn-1,3;fn,4= 3*fn-1,4+fn-1,1+fn-1,2+fn-1,3;接着在进行一些简化：首先从上面的递推式可以清楚地看到 fn的计算只

4、与 fn-1有关，可以只fn-1就可以了。其次，用这样递推的方法，只需在开始时对 xy 进行二进制的转换，接着根据其每一位上的值是 1 还是0 进行计算就可以了。时间复杂度：O(n*k1)，其中 k1 正比于高精度加法的时间。空间复杂度也正比于n+k1。其中 n1 begin:eger;then exit;thenfor i:=1 to x0 do beginz:=(xi+y)mod 2;xi:=(xi+y)div 2; y:=10*z;end; end else beginy:=10;for i:=2 to x0 do beginxi-1:=(xi+y)div 2;y:=(xi+y) mod

5、 2)*10;end; dec(x0);end;end; beginfillchar(tx,sizeof(tx),0); fillchar(ty,sizeof(ty),0); for i:=0 to n-1 dobegintxi:=xx0 mod 2;tyi:=yy0 mod 2; divide(x);divide(y); end;end;procedure add(var a:stype;b var i,x,y,zbeginx:=0;y:=0;:stype);高精度加法过程:eger;if a0b0 then z:=a0 for i:=1 to z dobeginelse z:=b0;y:=

6、(ai+bi+x)div 10;ai:=(ai+bi+x) mod 10; x:=y;end; a0:=z;if x0 then begin inc(a0);aa0:=x;end;end;procedure make;主过程 var i,jbeginfillchar(f,sizeof(f),0); f1,0:=1;f1,1:=1;for i:=1 to n do beginif txi-1=0 then begin:eger;if tyi-1=0 thenx,y2(n-1) beginnow:=f1; add(f1,now);add(f1,now); for j:=2 to 4 doadd(f

7、1,fj);end elsebeginx=2(n-1) now:=f3;add(f3,now);add(f3,now);add(f3,f1);add(f3,f4); add(f1,f2);ad,f2);fillchar(f2,sizeof(f2),0); end;end else beginif tyi-1=0 thenx=2(n-1),y=2(n-1) now:=f4;ad for,now);ad j:=1 to 3 do ad,now);,fj)endendendend;procedure out;输出 var ibegin:eger;for i:=f1,0 downto 1 do write(f1,i);wrin;close(outp