反斗奇兵: Exhausion & Patterning

小弟一直都不喜歡做剪枝的exhaustion題... 所以今次想介紹一些不是直接exhaustion的頹題但又不是用剪枝法的題型

還記得JOE神講過的 HKOI 2006 Senior - Toggle 嗎?

題目大意:

有一個N*N的matrix﹐初始時每一格的value都是0 or 1
每一步可以把一整列或一整欄的0變做1，1變做0
目標是找出一種方法使整個matrix所有value變做0
(N<=18)

Sample:
N=4
0 0 1 0
0 0 1 0
1 1 0 1
0 0 1 0

解法: 反第3欄和第3列

這題是dp? greedy?
如果沒估錯的話，以上2種方法都做不到的... 那就只剩下exhausion了... 但 O(2^(2n)) 又會TLE

Observation 1: 反row/column的次序不影響結果 事實上，m[i][j] 的最終value 只是取決於反row i 與反column j 的次數之和

Observation 2:
每column/row不會反>1次
明顯地，反2次=白反(不是白飯)，反3次=反1次...

所以，正確解法就是
exhaustion反哪些column，之後對於每一row，若全部=0就不反，全部=1就反，部份=1就代表exhaustion出來的反column組合不正確

Time complexity: O(N^2 * 2^N)

做這些題目，重點就是觀察形狀和特性，甚至不用exhaustion也能solve到

例子:

pku 3363 - Annoying painting tool
pku 3279 - Fliptile

加多題，

pku 3600 - Subimage Recognition

下面是這2條的解法

-------------------------------------------------------

pku 3363 - Annoying painting tool

題目大意:
和 Toggle 差不多，不過每次反一個r*c的長方形

(反該點 = 以該點為r*c長方形左上角來反)

Observation:
照舊，同一點不會反>1次，反的順序沒關係...

解法:
由最左上方至最右下方的次序來做，如果該點=1就反
因為若「此時不反，時機己晚」，由於是"左至右，上至下"的做，做到此時只剩下反這點可以使這點變做0
當然，反這點的長方形不能出界...
若果最後不能把所有變做0，則是no solution

sample:
4 3 2 1
011
110
011
110

011 // 不用反
110
011
110

001 // 反!
100
011
110

000 // 反!
101
011
110

000
001 // 反!
111
110

000
001 // 不用反
111
110

000
000 // 反!
110
110

000
000
010 // 反!
010

000
000
000 // 反!
000

000
000
000 // 不反
000

最後一列也要做，check有沒有漏下'1'未反，若有，即no solution

至於反後怎樣update個matrix
若O(r*c) 的反，整個time complexity = O(N^2*M^2)，很慢

其實每次反可視為把那該長方形內每格的count[i][j]+1
做到(i,j)時，該格的最新數值 = (matrix[i][j]+count[i][j])%2

要做到[修改一堆，query 1點]...
當然是...
2D BIT!
當然segment tree也可...
[修改一堆，query 1點] 的細節另文再談或等BIT之神whh講...

Time complexity = O(N*M*lg(N)*lg(M))

-------------------------------------------------------

pku 3279 - Fliptile

也是和 toggle 差不多，不過每次是反一個十字 (可反出界)

解法:
exhaustion第一列的反pattern，之後由第2行往下做，每一行左至右的掃，反不反是"沒有選擇餘地的"

Time complexity = O(2^N*M*N)

總結: 做這些題目要夠狠心，要令那些格沒有「反不反」的選擇餘地