形成區(qū)域題解-奇跡解題報(bào)告

1、形成區(qū)域（解題）最簡(jiǎn)單的方法是灌水法了，雖然很可能行不通的，但大多數(shù)朋友還是會(huì)去試一試的，因?yàn)檫@是第一，也是最容易實(shí)現(xiàn)的。灌水法：fillchar (map,sizeof(map),1);for l:=1 to n do 放置每一個(gè)矩形for i:=x1l to x2l-1 do for j:=y1l to y2l domapi,j:=colorl;最后對(duì) map 整體掃描一遍便到各種顏色的面積。很可惜的是空間運(yùn)行是遠(yuǎn)遠(yuǎn)不夠的，只能換個(gè)角度了基于對(duì)各個(gè)格子的考慮。也可以容易的寫出下面的代碼：for i:=1 to a do for j:=1 to b dofor l:=n downto 0 d

2、o第 0 個(gè)矩形為矩形（a,b）,color0=1 if (x1l=i) and (y1l=j)then beginmapi,j:=colorl; break;end.兩個(gè)算法只是角度不一樣，復(fù)雜度都是 O（nab）。但后一個(gè)空間比前一個(gè)小的多，且速度快的多（多了個(gè) break）。這個(gè)算法可以過 10 個(gè)數(shù)據(jù)，一共 11 個(gè)數(shù)據(jù)（usaco 老是出一些 bt 的數(shù)據(jù)）.O(nab)的復(fù)雜度，對(duì)付 n=1000，a=b=10000 的數(shù)據(jù)顯然是行不通的。第十一個(gè)數(shù)據(jù)就是這樣的一個(gè)數(shù)據(jù)。上面的算法到底是慢在那里呢？基于上述算法，對(duì)每一個(gè) 1*1 的方格都處理了一次。很顯然這是不必要的。的方格可以連

3、在一起處理。所以也就很自然的想到了離散化：兩個(gè)數(shù)組分別放置矩形的橫坐標(biāo)和縱坐標(biāo)。Py6Py5Py4Py3Py3Py1Px1px2px3px4px5px6很容易發(fā)現(xiàn)這些離散化后的小矩形中的各個(gè)方格的顏色是相同的。在每一個(gè)離散矩形里選出一 1*1 的方格作為代表，計(jì)算它的顏色。這樣就可以在一次中處理一個(gè)離散矩形里的顏色屬性。離散化顯然是比原來的算法更進(jìn)一步，離散后復(fù)雜度降到 O（4n3）。對(duì)付 n=1000的數(shù)據(jù)還是弱了點(diǎn)（還是只能過 10 數(shù)據(jù)）。仔細(xì)想。離散化后還是做了很多的不必要的工作。Py6Py5Py4Py3Py3Py1Px1px2px3px4px5px6如圖，用前面的算法，要確定 5*5

4、=25 個(gè)矩形的顏色。而實(shí)際上只有 3 重顏色，4個(gè)區(qū)域（實(shí)線圍成），按照區(qū)域算，也只要確定 4 個(gè)區(qū)域的顏色屬性，而不是 25 個(gè)。算法之所以慢的原因也就照到了：做了大量的不必要的工作?，F(xiàn)在的格子，做最精簡(jiǎn)的工作。怎么有效的去合并這些相同屬性的子問題？是現(xiàn)在要做的是合并這些相同屬性的首要問題。在原來算法的基礎(chǔ)上，很容易想到的是用該區(qū)域的面積。填充法。以深搜時(shí)搜到某個(gè)區(qū)域的第一個(gè)格子為代表，本題不僅在時(shí)間上很苛刻，在空間上的必須考慮算法的有效性。也是制約算法實(shí)現(xiàn)的難點(diǎn)，所以些出的算法在 dfs 前預(yù)處理用一數(shù)組相鄰格子之間的連通情況（虛線為連通，實(shí)現(xiàn)我不連通）?；诳臻g上的開銷太大，還是要采用

5、離散，并對(duì)每個(gè)矩形進(jìn)行壓縮。離散后的空間開銷只有 86 的 booolean 數(shù)組，壓縮矩形后處理邊的連用情況也快的多了。當(dāng)然也不一定要像上面的算法那樣把能合并的都合并了，其實(shí)只要不去做太多無謂的工作，一樣可以得到很不錯(cuò)的效果?；诖说乃惴?。的矩形切割和線段樹就是很不錯(cuò)矩形切割：此把矩形（a,b）看成是最先加入的矩形，顏色為 1。然后每次依次加入矩形，將與其的矩形分割后加入隊(duì)列之后（去掉的部分）。最后掃描一次隊(duì)列即出各個(gè)顏色的面積。(x2,y2)(wx1,y2)具體分割方法如下：(x2,wy2)(x1,wy1)(x1,y1)(wx2,y1)矩形用一個(gè)線段坐標(biāo)表示部分:pxi為加入矩形的坐標(biāo)矩形(x1,y1,x2,y2)為被分割矩形的被分割出的矩形面積為 0。黃域是兩個(gè)矩形的 wx1=max(x1,px1); wx2=min(x2,px2); wy1=max(y1,py1); wy2=min(y2,py2);上圖只是一般情況，線段樹：上面所提到的算法都是動(dòng)態(tài)處理的，還可以寫出基于線段樹的靜態(tài)處理的方法。如果采用二維線段樹（每次最多有 4 個(gè)下降分支），復(fù)雜度為 O(4nlogn)。由于空間的限制，必須進(jìn)行壓縮，這一點(diǎn)還不夠，還要使用動(dòng)態(tài)線段樹處理才能突破空間這個(gè)頭痛現(xiàn)起來太繁瑣。實(shí)為了解決空間這個(gè)難題，不得不犧牲時(shí)間換空間