1、WC 2005信息學奧林 克 令營測試題 解題 告Prem erC2 05 ro雙面棋盤（Dface朱園題述n 行有一白棋盤 每格子都有面 一面色，一面黑色。把棋盤平放在桌子上，因此每個格子恰好一面朝上，如下圖所示：把每行從上到下為 1，2，3，n，各列從左到右為 1，2，3，n，則每個格子可以用棋盤坐標(x, y)表示。在上圖中，有 8 個格子黑色朝上，另外 17 個格子白色朝上。如果兩個同色格子有一條公共邊，稱這兩個同色格子屬于同通塊。上圖共有 5 個黑色連通塊和 3 個白色連通塊?？梢悦糠昼妼⒁粋€格子翻轉（即白色變成黑色，黑色變成白色），然后計算當前有多少個黑色連通塊和白色連通塊，你能算

2、得更快嗎？輸入文件的第一行包含一個正整數(shù) n，為格子的邊長。以下 n 行每行 n 個整數(shù)，非 0 即 1，表示初始狀態(tài)。0 表示白色，1 表示黑色。下一行包含一個整數(shù) m，表示操作的數(shù)目。以下 m 行每行兩個整數(shù) x, y (1 x, y n)，表示把坐標為(x, y)的格子翻轉。輸出文件包含 m 行，每行對應一個操作。該行包括兩個整數(shù) b, w，表示黑色Page 1 of 8輸出文件輸入文件0 5 全 信 學奧林 克 令 測 題 解題lem2雙面 盤（Dface）京 外 語 校 朱 園區(qū)和色域目1 n 2 01 m 1 ,0翻轉 3)后，棋盤變?yōu)椋河?4 個黑域和 3 個白域翻轉(2, 3)

3、之后，棋盤變?yōu)椋河?5 個黑域和 2 個白域問題簡述給定 n*n 的黑白棋盤（1 n 200），共有 1 m 10,000 個修改命令。每個命令，將棋盤中的某個位置的黑白顛倒。要求計算每個命令過后棋盤上的黑、白4-連通塊個數(shù)。Page 2 of 8樣說d a eDfa e.10124 35輸輸樣約C信息學奧林匹 冬令營測試題 解題Probl m2雙面 盤每次修改命令過后，整個棋盤新行 F oodfill，總復雜度為O(n2m) 。這個算法非常慢，但是可改進的空間非常大。因為很多已有連通塊，被重新計算。最簡單的改進措施是，從當前命令修改位置的4 個相鄰塊開始，進行Floodfill，將修改前后棋

4、盤的不同之處，用盡可能少的操作算出來。對隨機數(shù)據(jù)這個算法可以很快地結束（賽后證明測試數(shù)據(jù)不強，這個算法可以對 70 分），但是倘若棋盤大部分都是白色，只有零星的黑色小連通塊，該算陷入和前面一樣的O(n2m) 復雜度，并且超時嚴重。繼續(xù)尋找上述算法中的冗余，如這樣一例（當前修改的是紅色格子）：其實只要知道它周圍 4 個格子的連通性即可，而并不需要關心這些格子所在的完整連通塊。通常情況下，對這 4 個格子中的任意兩個做寬搜，都可以在很少的步數(shù)內完成。得到了他們的連通信息之后，可以通過仔細的黑白連通塊增減計算，得出新棋盤的完整連通信息。這個算法幾乎可以通過所有數(shù)據(jù)，官方沒有給出針對性數(shù)據(jù)，因此可以拿

5、到滿分。當然，立志于尋找一個更穩(wěn)定的通用算法。對行集合建立線段樹，區(qū)間i,j表示第 i 行到第 j 行的“連通情況”。具體來說，可以用兩個長度為 n 的數(shù)組，分別第 i 行和第 j 行的每個格子的顏色，Page 3 of 8算法 2算法 1茅WC 0 5 全 信息 奧 匹 冬 營京市 國 學a e澤園滿足：ij 行內連通的格子，被賦予相同色；否分不同的顏色如下圖1122215間 ,j應分為兩個子區(qū)間i,mid和mid+1既然是線段樹中mi( +j) div 2。根據(jù)第 mid 行和 mid+1 行的相鄰信息，可以將第 i 和 j 行的顏色進行合并，復雜度為 O(n)。接下來，對每個區(qū)間i,j，

6、的兩色連通塊個數(shù)（不包含第 i、j區(qū)間行格子所在的連通塊）。區(qū)間合并時，當前區(qū)間內的連通塊個數(shù)，等于兩個子區(qū)間的連通塊個數(shù)，加上 mid 行和 mid+1 行所確定的，但不在 i 行和 j 行內的新連通塊個數(shù)。有了這個數(shù)據(jù)結構，可以做本題了。每接到一個修改顏色的指令后，我們修改它所在的 O(logn)層線段樹結點，每層需要 O(n)的復雜度。修改完畢之后，2n-1 行的兩色連通塊個數(shù)，再用 O(n)時間把外部（第調用根節(jié)點1、n 行所在的）連通塊分別算出來。本算法的時間復雜度為 O(mnlogn)，常數(shù)小。上述算法在每一層都需要計算整行的 n 個元素的合并，其中不免出現(xiàn)冗余。為了更有效地進行動

7、態(tài)更新，到了對平面進行 4 分的策略。與前面的定義類似，用x1,y1,x2,y2表示 x1x2 行，y1y2 行所組成的矩形，在該節(jié)點位置不僅該矩形的上下邊界的連通情況，而是四周邊界的所有格子的顏色。如圖Page 4 of 8算法 3W0 5息 奧 匹克題報emDf c ）南 市外 語 校1122211113445可以四分（分為 4 個子矩形 ，但是那樣程較難實現(xiàn)。對當前矩形體，我采的是分策。找到當長的一邊，將矩形分為等積的兩部分。log )級別。但每次更格子的顏色需要問的節(jié)點仍然是發(fā)現(xiàn)，著層數(shù)的增加，合并矩形的卻在降?？勺C明有的 O(l g 的節(jié)點的新共需(n)的時間復雜度。因此該算法的總時

8、間復雜度為 O(mn)，可惜常數(shù)項非常大。這三個程序的具體效率參見附錄。程序算法 1 對應程序 dface_n2(improve).cxx，以 BFS 為，判斷某兩點是否連通，實現(xiàn)沒有大礙。算法 2 對應程序 dface_nlogn(div2).cxx，以如下結構表示線段樹struct TTreel, r, mid;/第 lr 行，分為l,mid和mid+1,r兩個子區(qū)間TTree *lc, *rc;/左右孩子c2MaxN;/c0和 c1l 和 r 行的顏色b, w;/b/w兩色連通塊個數(shù)在具體實現(xiàn)之時，對兩行合并我使用了并查集。雖說這是個無謂之舉，可以Page 5 of 8數(shù)據(jù)結構&算法設計

9、C 2005信息學冬令 測試題 解題報 Pr b em2雙面 盤（Df c市外國 學校操作代替，但是并集犧牲很的時間，換來了編雜度很輕松地程序湊合在一起。3 對應程序 dface_n div2).cxxine _VER 1下結構表矩形樹：fineHORstteeusigne ch r x11,x2,y2, mid,mi 1;/ h=x -x1+1, w= 2 y1+1char type;/type2，分別代表當前矩形被橫向或縱向割TTr e *lc, *rc;/左右unsi ned short*c;/動態(tài)開 chw組記邊格的色un igned hort it b1,w ; /部黑白連通塊個數(shù)。

10、的不同在于，里用一個二維組c0. -10. w-1來記邊界格子和算法的色，就是說中的位置是浪費。空間復雜度O(n)上升了O(n2)是編度低了少。（使用 1024*768 分辨率+Windows Notepad 可達到視覺最佳效果）dface_n2(improve).cxx dface_nlogn(div2).cxx dface_n(div2).cxxPage 6 of 8測試點12345n2改進算法 1 C+0.005s0.007s0.005s0.053s0.087snlogn算法 2 C+0.005s0.005s0.006s0.591s1.140sn算法 3C+0.004s0.006s0.0

11、08s0.713s1.379s程序結果程序WC 2005 全 信息學奧林匹 冬令營測試題 解題 roblem 面 盤 D ac ）市外 語學校8se時限：測試環(huán)境與標準環(huán)境詳見附錄。總結基本的算法，不斷尋找余，步步目標，是道題目的主策略。做題過程，也不斷著難的取。個人認為，賽場上編雜度為取的。優(yōu)秀的算法，終無法編完程序，或無調試正確，或喪大分測試，實在惜。因此計算法之前，應該對算法的現(xiàn)以及實際效，做出仔細預期分析。附測環(huán)境編譯器 Dj pp3.2.1 + Rhide 1.5. 1-W o de recated -O6 -march=pentium3 - Freepascal 1.0.6 -Op

12、3st-math -fomit-frame-poer機型el Celeron prosor 735 + 128MB RAMWindows 2003 Server Entrise Edition + Dos for 2003測試環(huán)境編譯器 Djgpp3.3.5-8 + Rhide 1.5-1-pipe -O6 -march=pentium3 -st-math -fomit-frame-poerPage 7 of 8測試環(huán)境與標準環(huán)境標準程序 +0.00 s0.00 s0.0021.265s2 536s測點679102改進算法 1 C+0. 29s1 138s1 289s0 137s2 .703slogn算法 C+1.53 s1.99 s4.6353.638s2.767s法 3C1.s5.751s4.9 05.16 s標準程序 +3.396s4.090s12. 51s11.381s9.4 6s2005信息學冬令營測 題 解題Pro lem