形成区域题解-奇迹解题报告

1、形成区域（解题）最简单的方法是灌水法了，虽然很可能行不通的，但大多数朋友还是会去试一试的，因为这是第一，也是最容易实现的。灌水法：fillchar (map,sizeof(map),1);for l:=1 to n do 放置每一个矩形for i:=x1l to x2l-1 do for j:=y1l to y2l domapi,j:=colorl;最后对 map 整体扫描一遍便到各种颜色的面积。很可惜的是空间运行是远远不够的，只能换个角度了基于对各个格子的考虑。也可以容易的写出下面的代码：for i:=1 to a do for j:=1 to b dofor l:=n downto 0 d

2、o第 0 个矩形为矩形（a,b）,color0=1 if (x1l=i) and (y1l=j)then beginmapi,j:=colorl; break;end.两个算法只是角度不一样，复杂度都是 O（nab）。但后一个空间比前一个小的多，且速度快的多（多了个 break）。这个算法可以过 10 个数据，一共 11 个数据（usaco 老是出一些 bt 的数据）.O(nab)的复杂度，对付 n=1000，a=b=10000 的数据显然是行不通的。第十一个数据就是这样的一个数据。上面的算法到底是慢在那里呢？基于上述算法，对每一个 1*1 的方格都处理了一次。很显然这是不必要的。的方格可以连

3、在一起处理。所以也就很自然的想到了离散化：两个数组分别放置矩形的横坐标和纵坐标。Py6Py5Py4Py3Py3Py1Px1px2px3px4px5px6很容易发现这些离散化后的小矩形中的各个方格的颜色是相同的。在每一个离散矩形里选出一 1*1 的方格作为代表，计算它的颜色。这样就可以在一次中处理一个离散矩形里的颜色属性。离散化显然是比原来的算法更进一步，离散后复杂度降到 O（4n3）。对付 n=1000的数据还是弱了点（还是只能过 10 数据）。仔细想。离散化后还是做了很多的不必要的工作。Py6Py5Py4Py3Py3Py1Px1px2px3px4px5px6如图，用前面的算法，要确定 5*5

4、=25 个矩形的颜色。而实际上只有 3 重颜色，4个区域（实线围成），按照区域算，也只要确定 4 个区域的颜色属性，而不是 25 个。算法之所以慢的原因也就照到了：做了大量的不必要的工作。现在的格子，做最精简的工作。怎么有效的去合并这些相同属性的子问题？是现在要做的是合并这些相同属性的首要问题。在原来算法的基础上，很容易想到的是用该区域的面积。填充法。以深搜时搜到某个区域的第一个格子为代表，本题不仅在时间上很苛刻，在空间上的必须考虑算法的有效性。也是制约算法实现的难点，所以些出的算法在 dfs 前预处理用一数组相邻格子之间的连通情况（虚线为连通，实现我不连通）。基于空间上的开销太大，还是要采用

5、离散，并对每个矩形进行压缩。离散后的空间开销只有 86 的 booolean 数组，压缩矩形后处理边的连用情况也快的多了。当然也不一定要像上面的算法那样把能合并的都合并了，其实只要不去做太多无谓的工作，一样可以得到很不错的效果。基于此的算法。的矩形切割和线段树就是很不错矩形切割：此把矩形（a,b）看成是最先加入的矩形，颜色为 1。然后每次依次加入矩形，将与其的矩形分割后加入队列之后（去掉的部分）。最后扫描一次队列即出各个颜色的面积。(x2,y2)(wx1,y2)具体分割方法如下：(x2,wy2)(x1,wy1)(x1,y1)(wx2,y1)矩形用一个线段坐标表示部分:pxi为加入矩形的坐标矩形(x1,y1,x2,y2)为被分割矩形的被分割出的矩形面积为 0。黄域是两个矩形的 wx1=max(x1,px1); wx2=min(x2,px2); wy1=max(y1,py1); wy2=min(y2,py2);上图只是一般情况，线段树：上面所提到的算法都是动态处理的，还可以写出基于线段树的静态处理的方法。如果采用二维线段树（每次最多有 4 个下降分支），复杂度为 O(4nlogn)。由于空间的限制，必须进行压缩，这一点还不够，还要使用动态线段树处理才能突破空间这个头痛现起来太繁琐。实为了解决空间这个难题，不得不牺牲时间换空间