集训队作业p9801解题报告

1、Painters Studio9801(1-1)解题报告长郡中学 金恺试题翻译：画家准备在画室内创作许多幅画。绘画过程需要各种尺寸的方形矩阵。尺寸为i的方形矩阵含有2i行和2i列，在部分行和列的交叉处有一些洞。尺寸为0的矩阵有一个洞，对于i0，尺寸为i的矩阵是由4个尺寸为2（i1）2（i1）的正方形构成。看下面的图（“bez otworow”意思是“没有洞”在板上，“ matry stopnia ”意思是“矩阵的尺寸”。）在右边的两个正方形和在左下方的正方形是尺寸为i1的矩形，左上方的正方形没有洞。图画是以下面的方式构成的。首先，我们准备3个非负整数N，X，Y；接着，我们拿2个尺寸为N的矩形将

2、其中一个叠放在另外一个上面，并且将上面的矩形向右移动X列，向上移动Y行，我们将这样一种模型放在白色的帆布上，并且将黄色颜料涂在矩形的公共部分。通过这种办法，我们就在帆布上到黄色图案，显然图案是在两个矩形公共的洞的地方产生的。例如，考虑两个尺寸为2的矩形，我们将上面的矩形向右移2列，然后向上移两行，有3个洞重合，如上面的右图所示。【任务】编写程序：从文件MALIN中读两个矩形的尺寸和上面移动矩形的移动行、列数；计算在帆布上的黄色图案数目；将结果写入MALOUT中。【输入】：文件MALIN的第一行有一个正整数N，0=N=100，这个数是用来构造图画的矩形的尺寸；第二行有一个整数X，第三行有一个整数

3、Y，0=X，Y=2n；整数X是位于上面的矩形移动的列数，Y是移动的行数。【输出】：输出文件只有一行，就是帆布上所有黄色图案的总数。试题分析：这道题目很明显不能用穷举法来做，因为数据量太大，不可能存下整个矩形的数据，所以不妨尝试用分治的方法，将两个尺寸为N的大矩形的重叠部分，分解成若干个尺寸为N-1的小矩形的重叠部分的和来处理。如图a：图a两个尺寸为N的矩形的重叠部分可以分解为六个尺寸为N-1的小矩形的重叠部分来计算：+图a用这种方法来搜索，复杂度为，显然需要大量优化。通过不断的深入研究，可以发现一条很重要的性质。如图b：112411343图b图b-1图b-2图b-1是两个尺寸为N的矩形，取其中

4、的一个蓝色N-1矩形和三个N-1黄色矩形为例来进行分析，如图b-2。图b-2中用红、紫、蓝、黑四种颜色来表示这四个矩形，而且这四个尺寸为N-1矩形又各自被分割为了四个尺寸为N-2的小矩形。图b-1中的绿色重叠的有效部分在图b-2中就是有标号的这一部分，很显然，其中标号相同的部分是全等的。再分析，黑矩形和红矩形的重叠部分要用到1、2、3、4这四部分的结果，而黑色矩形与紫色矩形只要用到4这一块的结果，黑色矩形和蓝色矩形只要用到3这一块的结果，如果求出了1、2、3、4这四部分的结果，就既可以推出红黑重叠部分结果，又可以知道紫黑、蓝黑重叠部分的结果了。可以这么说，紫黑、蓝黑重叠部分可以在红黑重叠部分中

5、找到。在计算红黑重叠部分的过程中，就可以顺便把紫黑、蓝黑重叠部分计算出来，于是，可以说计算左图中绿色部分的主要任务就是计算右图中红黑重叠部分的结果。现在回到图a，因为图中部分可以在中找到，计算尺寸为N的两矩形的重叠部分，其主要任务就是计算的结果，在计算的过程中，都可以被顺便的算出来，知道的结果，就可以求出最后的总结果。而计算N-1的又只要计算N-2的四种情况中的一种情况。这样，每计算一个尺寸为K的矩形的结果时，都只要计算尺寸为K-1的矩形重叠情况中的一种情况，复杂度一下子降到了，很快就能出解了。空间的要求也非常小：启发与总结：此题思考的难度很大，特别使要找出每种尺寸的本质不同的相交情况只有4种

6、这一规律比较困难。但找到后编程还是比较容易的。程序清单：$S-,X-,Y-,N+$M 65521,0,655360program Mal;const Fn1 = Mal.In; Fn2 = Mal.Out; BaseNumber = 8; MaxN = 100;type TypeBasic = array 0 . 7 of Longint; TypeSave = array 1 . 4, 0 . MaxN of TypeBasic; TypeSign = array 1 . 2, 0 . MaxN of Boolean; TypeGet = array 0 . MaxN, 0 . 1, 0 .

7、 1 of TypeBasic;var Save: TypeSave; Sign: TypeSign; Get: TypeGet; n, Base: Longint;function Compare(ordinal1, Number1, ordinal2, Number2: Integer): Boolean;var i: Longint;begin Compare := True; if Saveordinal1, Number1, 0 Saveordinal2, Number2, i then begin Compare := True; Exit end else if Saveordi

8、nal1, Number1, i Savenum3, Number3, i then begin Savenum3, Number3, i + 1 := Savenum3, Number3, i + 1 - 1; Savenum3, Number3, i := Savenum3, Number3, i + Base end; Savenum3, Number3, i := Savenum3, Number3, i - Saveordinal2, Number2, i end; while (Savenum3, Number3, 0 1) and (Savenum3, Number3, Save

9、num3, Number3, 0 = 0) do Dec(Savenum3, Number3, 0); if (Savenum3, Number3, 0 = 1) and (Savenum3, Number3, 1 = 0) then begin Savenum3, Number3, 0 := 0; Signnum3, Number3 := True endend;procedure Multiply(crood, Number, Multiplicand: Integer);var i, t: Longint;begin t := 0; for i := 1 to Savecrood, Nu

10、mber, 0 do begin Savecrood, Number, i := Savecrood, Number, i * Multiplicand + t; if Savecrood, Number, i Base then begin t := Savecrood, Number, i DIV Base; Savecrood, Number, i := Savecrood, Number, i MOD Base end else t := 0 end; if t 0 then begin Inc(Savecrood, Number, 0); Savecrood, Number, Sav

11、ecrood, Number, 0 := t endend;procedure Add_Multiply(ordinal1, Number1, ordinal2, Number2, Number: Integer);var i, t: Longint;begin t := 0; for i := 1 to Saveordinal2, Number2, 0 do begin Saveordinal1, Number1, i := Saveordinal1, Number1, i + Saveordinal2, Number2, i * Number + t; if Saveordinal1, N

12、umber1, i Base then begin t := Saveordinal1, Number1, i DIV Base; Saveordinal1, Number1, i := Saveordinal1, Number1, i MOD Base end else t := 0; Saveordinal2, Number2, i := 0; end; Saveordinal2, Number2, 0 := 0; if t 0 then begin Inc(i); Saveordinal1, Number1, i := Saveordinal1, Number1, i + t end;

13、if Saveordinal1, Number1, 0 0 then p := BaseNumber - p; Inc(j, p); for i := j downto 1 do helpi + p := helpi; for i := 1 to p do helpi := 0; for i := 1 to Saveordinal, Number, 0 do begin t := j - i * BaseNumber + 1; Saveordinal, Number, i := 0; for k := 1 to BaseNumber do Saveordinal, Number, i := S

14、aveordinal, Number, i * 10 + helpt + k - 1; end; if Saveordinal, Number, 0 = 0 then Saveordinal, Number, 0 := 1; if (Saveordinal, Number, 0 = 1) and (Saveordinal, Number, 1 = 0) then Saveordinal, Number, 0 := 0 end;begin FillZero; Assign(Input, Fn1); Reset(Input); Readln(n); Into(1, n); Into(2, n);

15、Close(Input)end;procedure Print(Ordinal, Number: Integer);var i, t: Integer; e: Extended;begin write(Saveordinal, Number, Saveordinal, Number, 0); for i := Saveordinal, Number, 0 - 1 downto 1 do begin e := 1; for t := 2 to BaseNumber do begin e := e * 10; if Saveordinal, Number, i 0 then begin j :=

16、ord(Sign1, Deep); k := ord(Sign2, Deep); Save4, Deep := GetDeep, ord(Sign1, Deep), ord(Sign2, Deep); Exit end; xsmall := not Compare(1, Deep, 3, Deep - 1); ysmall := not Compare(2, Deep, 3, Deep - 1); if Save1, Deep, 0 0 then xbig := True else xbig := False; if Save2, Deep, 0 0 then ybig := True els

17、e ybig := False; if ysmall then begin if xbig then begin subtract(1, Deep, 3, Deep - 1, 1, Deep - 1); Save2, Deep - 1 := Save2, Deep; Sign2, Deep - 1 := Sign2, Deep; Search(Deep - 1); if Save4, Deep - 1, 0 0 then Add_Multiply(4, Deep, 4, Deep - 1, 1) end; if xsmall then begin Save1, Deep - 1 := Save

18、1, Deep; Sign1, Deep - 1 := Sign1, Deep; Save2, Deep - 1 := Save2, Deep; Sign2, Deep - 1 := Sign2, Deep; Search(Deep - 1); if Save4, Deep - 1, 0 0 then Add_Multiply(4, Deep, 4, Deep - 1, 3) end end; if ybig then begin if xbig and not(Sign1, Deep xor Sign2, Deep) then begin subtract(1, Deep, 3, Deep - 1, 1, Deep - 1); subtract(2, De