POJ 1222 1681 1830 3185 開關燈問題 (高斯消元 異或方程組)

POJ 1222?EXTENDED LIGHTS OUT 基本的開關燈問題.還保證唯一解. 我們把每一個燈泡當成一個狀態xi，總共有30個，而且每個燈與其他燈的關系也很明顯。所以我們就可以列30方程30個變元的方程組： xi = 1 * xi + 1 ?* x(i-1) + 1 * x(i+1) + 1 * x(i-6) + 1 * x(i+6) = 1 or 0 (mod 2) ? ? (0還是1看這個燈的初始狀態，即輸入數據) 這明顯就是裸的高斯消元了，題目還保證有唯一解。。。唯一的難點就是mod 2的處理，但是也不難，只要在行階梯矩陣回帶求解時取模就可以了~~~（具體看代碼吧） 代碼：http://www.shaidaima.com/source/view/11233 ? POJ 1681?Painter's Problem 開關燈模型，求解中1最少的方案(求最優解)。此時我們往往需要枚舉自由變元的狀態來求出多解，但此題數據較弱，不需枚舉,每次將自由變元置為0可過. 代碼：http://www.shaidaima.com/source/view/11234 ? POJ 1830 開關問題 開關燈問題，求解的個數。更簡單，唯一解輸出1，多解時解的個數就是(2^自由變元個數). 不過這題我把它換用異或方程組做，即： M[0][0]x[0]^M[0][1]x[1]^…^M[0][N-1]x[N-1]=B[0] M[1][0]x[0]^M[1][1]x[1]^…^M[1][N-1]x[N-1]=B[1] … M[N-1][0]x[0]^M[N-1][1]x[1]^…^M[N-1][N-1]x[N-1]=B[N-1] ★：解異或方程也可以套用高斯消元法，只須將原來的加減操作替換成異或操作就可以了，兩個方程的左邊異或之后，它們的公共項就沒有了。 具體的操作方法是這樣的：對于k=0..N-1，找到一個M[i][k]不為0的行i，把它與第k行交換，用第k行去異或下面所有M[i][j]不為0的行i，消去它們的第k個系數，這樣就將原矩陣化成了上三角矩陣；最后一行只有一個未知數，這個未知數就已經求出來了，用它跟上面所有含有這個未知數的方程異或，就消去了所有的著個未知數，此時倒數第二行也只有一個未知數，它就被求出來了，用這樣的方法可以自下而上求出所有未知數。 代碼：http://www.shaidaima.com/source/view/11235 ? POJ 3185?The Water Bowls 開關燈問題，和POJ1681一樣，不過這題數據可沒那么好糊弄，要枚舉自由元了~還有怎么求解異或方程組…… 代碼：http://www.shaidaima.com/source/view/11236