集訓隊作業(yè)transversal解題報告

1、1Transversal 解題河北唐山一中 鬲融題目描述有一個(2n+1)*(2n+1)的網(wǎng)格，其中有的格子包含一個“+”，另外的格子包含一個“-”。每次可以選擇 2n+1 個格子，使任兩個格子不也不同列，然后把這些格子里的符號改變，即“+”變成“-”，“-”變成“+”。給出一個初始狀態(tài)，求一種改變顏色的方案，使得最后只有不超過 2n 個格子里有加號。輸入輸入的第一行包含一個整數(shù)n(1n20)。以下 2n+1 行包含初始的網(wǎng)格。輸出如果目標不可能實現(xiàn)輸出一行“No solution”。否則在第一行輸出“There is a solution:”，以后每行有 2n+1 個數(shù)，表示一個操作。在第

2、i 個位置的數(shù)是j 表示要改變第i 行第 j 列上的符號。如果有多種解只需給出一組。樣例輸入1+-+-+樣例輸出There is a solution:121323313122解法分析題目要求的目標狀態(tài)只是使加號個數(shù)小于 2n+1，這似乎并不們設想可能沒有無解的情況，所有數(shù)據(jù)都可以構造出解。構造法，所以我題目中定義的操作比較復雜，直接用這個操作構造并不容易，所以先通過這個操作找到一個簡單一點的操作，然后再進行構造。可以如果一個操作是a1, a2,ai,aj,a2n+1，那么在進行這個操作之后再進行a1, a2, , aj, , ai, , a2n+1 這個操作，結果就是使一個矩形的四個頂點改變

3、符號。這是一個非常簡單的操作，比較適合進行構造。1題目來源 URAL1092接下來就要通過這個操作來使“+”減少。顯然，如果存在一個矩形，有三個或以上頂點都是“+”，就可以通過一次操作使加號減少至少兩個。但是，這種情況并不一定出現(xiàn)。所以還需要進一步分析。雖然有三個頂點都是“+”的矩形并不一定存在，但是同一行或列上有兩個“+”還是比較普遍的，只要加號個數(shù)大于 2n+1 就一定可以保證。所以要處理的是下面的第一個圖形（用黑色表示加號，白色表示減號）。需通過兩次“矩形”操作，就可以使原來的 4 個加號減少兩個（如果圖中右上角和左下角原來也是加號還可以減少所以，當加號個數(shù)大于 2n+1 時，加號）?？?/p>

4、以使加號減少兩個。但是加號個數(shù)等于 2n+1 時也不符合要求，而且按這種方法不能處理。一般需要對特殊情況單獨進行，但是發(fā)現(xiàn)，改變一個格的符號，加號個數(shù)的奇偶性一定改變，而的構造法每次改變 4 個格的符號，所以有一個很重要的特點：加號個數(shù)的奇偶性不變。所以如果發(fā)現(xiàn)加號的個數(shù)是奇數(shù)，只要隨便進行一次操作（改變了 2n+1 個格的符號），就可以使加號的總數(shù)變成偶數(shù)，從而躲開有 2n+1 個加號的情形。構造法的復雜度在實現(xiàn)過程中，可以每一行每一列的加號個數(shù)。這樣就可以在 O(n)的時間內(nèi)找到兩個或同列的加號，從而使加號減少兩個。而這樣的操作次數(shù)是 O(n2)的，所以總的復雜度是 O(n3)的。注意到這

5、已經(jīng)是這種方法的下界，因為輸出的規(guī)模就可能達到 O(n3)。另一種思路：匹配題目中定義的操作確實比較復雜，但是也對有一定啟發(fā)。因為要求每行每列都有且僅有一個格子的符號改變，可以認為 2n+1 個行是一個二分圖的一部分，而 2n+1 列則是另外一部分。那么這個操作改變的格子就對應了這個二分圖上的一個完美匹配。如果把加號作為“有邊”，把減號作為“無邊”，那么就得到了一個二分圖，而每次操作就是找一個完美匹配，然后用這個匹配和原圖做對稱差運算（就是匹配上有的邊，如果原圖中有就去掉，沒有就加上）。而目標就變成了使這個圖的邊數(shù)小于 2n+1。一個很容易想到的貪心方法就是每次找一個最大匹配，然后補進一些不在

6、原圖上的邊形成完美匹配，最后進行這個操作。但是簡單的貪心是無效的，可能會進入死循環(huán)，比如下面這種情況：所以要對這種方法進行改進。首先來看一個簡單的結論：如果最大匹配包含的邊數(shù)是k，那么根據(jù)這個匹配進行一次操作后，邊數(shù)將會減小 2k-2n-1，這是很顯然的。因為新增了 2n+1-k條邊，減少了k 條邊，所以邊數(shù)的減小值就是 2k-2n-1。假設設至少有 2n+2 個加號，而最大匹配的邊數(shù)為 k，記二分圖的兩個點集為 X 和 Y，有匹配邊的點集合為 A 和 B，其中 X 包含 A，Y 包含 B。如果 A 和 B 之間有不是匹配邊的邊，那么進行兩次匹配之后，邊數(shù)一定減小，如下圖所示：證明：如果最大匹

7、配中邊數(shù)是 k，那么在進行操作后，在第二次匹配時，X-A和 Y-B 一定有一個匹配（這是操作時加進去的），而根據(jù)假設，A 和B 之間有不是匹配邊的邊，所以這兩個集合之間的最大匹配至少包含一條邊。那么第二次匹配得到的最大匹配邊數(shù)至少是(2n+1-k)+1，根據(jù)上面的公式計算，經(jīng)過這兩次匹配后，邊數(shù)至少要減小 2。但是，這樣一步的分析。是否就能保證在兩次匹配后邊數(shù)必然減小呢？這需要進行進使用反證法：仍然遵循上述假設，并設 A 和 B 之間只有那 k 條匹配邊，這樣X-A 和 Y-B 中的 4n+2-2k 個點至少要連 2n+2-k 條邊。這時論。分兩種情況討第一種情況如左圖：有一個在 X-A 或

8、Y-B 中的點發(fā)出了兩條邊，原來綠邊是匹配邊，只要把調(diào)整為匹配邊就可以了。第二中情況如右圖：由于沒有一個 X-A 或 Y-B 中的點發(fā)出兩條邊。進行了第依次操作后，X-A，Y-B 集合中存在了一個有 2n+1-k 條邊的匹配，但是原來它們向 A，B 兩個集合連有 2n+2-k 條邊。所以一定有一個匹配邊（設為 a1b1）滿足兩個頂點都有連向 A，B 集合的邊，設這些邊為 a1b2, a2b1,那么a2b1a1b2，就了一個可增廣軌。所以第二次操作時的最大匹配至少有2n+2-k 條邊，這樣根據(jù)前面的公式總邊數(shù)也減少了 2。所以無論如何，只要邊數(shù)大于 2n+1，總可以進行兩次匹配使邊數(shù)減少 2或

9、2 以上。當然，仍然需要處理邊數(shù)是 2n+1 的情況，這個處理方法和前面構造法完全一致，也是通過奇偶性來躲開 2n+1 這個麻煩的情況。一個改進注意到在證明匹配兩次邊數(shù)一定減小的時候有一步會給實現(xiàn)帶來一定的麻煩：在應用反證法的第一種情況時，對匹配邊進行了一個調(diào)整，當然可以真的去判斷這個情況并進行調(diào)整，而且也不影響效率，但是這樣便好象給算法打了一個補丁，使這個算法看起來很不舒服。另法是：把二分圖的兩個集合按度的大小排序。這樣可以證明（證明略，畫一個圖就可以看出來，很顯然的）一定不會出現(xiàn)需要調(diào)整的情況。這樣這個算法就比較漂亮了，用偽代碼寫出來就是建立二分圖if 邊數(shù)為奇數(shù) then 進行任意操作while 邊數(shù)2n do begin對頂點按度大小排序兩次匹配并進行操作 end;匹配算法的分析匹配算法的時間復雜度是 O(n5)的，但是一般情況應該接近 O(n4)，因為邊如果很多每次減少的也就較多，再加上匹配算法的實際效果也要比 O(n3)好，所以還