高斯消元入门②-异或线性方程组-POJ1222

题目大意:

给你一个 5 ∗ 6 5 * 6 5∗6大小的二维01矩阵代表灯的开关状态。改变任意一个灯的状态，会导致其上下左右的灯的状态的改变。问一种灯的开关方案使得最终所有灯都关闭.

题目思路:

首先，一个灯只会被按0次或1次。两次等于没按。不同灯按下的效果是叠加起来的.

解释:想象按下某个位置,等效于原矩阵异或上一个新矩阵。
例如按下 ( 2 , 2 ) (2,2) (2,2)产生的效果.

A 2 , 2 = [ 0 1 0 1 1 1 0 1 0 ] A_{2,2} = \left[\begin{array}{lll} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{array}\right] A2,2​=⎣⎡​010​111​010​⎦⎤​

那么 L → L ⊕ A 2 , 2 L \rightarrow L \oplus A_{2,2} L→L⊕A2,2​

数学表示为:

*设原矩阵为 L L L.令 X i , j X_{i,j} Xi,j​代表位置 ( i , j ) (i,j) (i,j)是否按下. A i , j A_{i,j} Ai,j​为效果矩阵。

有等式: L ⊕ ( X 1 , 1 ∗ A 1 , 1 ) ⊕ . . . ⊕ ( X n , m ∗ A n , m ) = 0 L \oplus (X_{1,1}*A_{1,1}) \oplus ... \oplus (X_{n,m}*A_{n,m})=0 L⊕(X1,1​∗A1,1​)⊕...⊕(Xn,m​∗An,m​)=0

( X 1 , 1 ∗ A 1 , 1 ) ⊕ . . . ⊕ ( X n , m ∗ A n , m ) = L (X_{1,1}*A_{1,1}) \oplus ... \oplus (X_{n,m}*A_{n,m})=L (X1,1​∗A1,1​)⊕...⊕(Xn,m​∗An,m​)=L

上面是用矩阵形式来表示的,对于每矩阵中每一位，可以有等式：

① X 1 , 1 ∗ A 1 , 1 [ 1 ] [ 1 ] ⊕ X 1 , 2 ∗ A 1 , 2 [ 1 ] [ 1 ] ⊕ . . . X n , m ∗ A n , m [ 1 ] [ 1 ] = L [ 1 ] [ 1 ] ①X_{1,1}*A_{1,1}[1][1] \oplus X_{1,2}*A_{1,2}[1][1] \oplus ... X_{n,m}*A_{n,m}[1][1] = L[1][1] ①X1,1​∗A1,1​[1][1]⊕X1,2​∗A1,2​[1][1]⊕...Xn,m​∗An,m​[1][1]=L[1][1]

② X 1 , 1 ∗ A 1 , 1 [ 1 ] [ 2 ] ⊕ X 1 , 2 ∗ A 1 , 2 [ 1 ] [ 2 ] ⊕ . . . X n , m ∗ A n , m [ 1 ] [ 2 ] = L [ 1 ] [ 2 ] ②X_{1,1}*A_{1,1}[1][2] \oplus X_{1,2}*A_{1,2}[1][2] \oplus ... X_{n,m}*A_{n,m}[1][2] = L[1][2] ②X1,1​∗A1,1​[1][2]⊕X1,2​∗A1,2​[1][2]⊕...Xn,m​∗An,m​[1][2]=L[1][2]

. . . ... ...

X 1 , 1 ∗ A 1 , 1 [ n ] [ m ] ⊕ X 1 , 2 ∗ A 1 , 2 [ n ] [ m ] ⊕ . . . X n , m ∗ A n , m [ n ] [ m ] = L [ n ] [ m ] X_{1,1}*A_{1,1}[n][m] \oplus X_{1,2}*A_{1,2}[n][m] \oplus ... X_{n,m}*A_{n,m}[n][m] = L[n][m] X1,1​∗A1,1​[n][m]⊕X1,2​∗A1,2​[n][m]⊕...Xn,m​∗An,m​[n][m]=L[n][m]

这样我们可以列出 n ∗ m n*m n∗m个方程，每个方程可以理解为所以点对某一个点的贡献等式.

这样我们就得到了一个异或线性方程组.利用高斯消元解决。

注意点:
1.如何消元?

1.老套路，但是注意，当其他行的对应未知数的系数为0时，就不要用当前行去相消。 也没必要消。所以只有当前行是1，且第x行为1时，当前行和第x行可以相消。
2.注意会有多解的情况.例如 L L L为全0矩阵.解有两个.所以同时声明两个变量 r , c r,c r,c来控制消元.具体看代码.

时间复杂度： O ( T ∗ ( n m ) 3 ) O(T*(nm)^3) O(T∗(nm)3)
AC代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
using namespace std;
const int maxn = 10 + 5;
int a[35][35] , b[8][8][8][8] , res[10][10];
int nx[10] = {0 , 0 , 0 , -1 , 1};
int ny[10] = {0 , -1 , 1 , 0 , 0};
int n = 5 , m = 6;
int main()
{
    ios::sync_with_stdio(false);
    // 预处理效果矩阵
    for (int i = 1 ; i <= n ; i++){
        for (int j = 1 ; j <= m ; j++){
            for (int k = 0 ; k <= 4 ; k++){
                b[i][j][i + nx[k]][j + ny[k]] = 1;
            }
        }
    }
    int t; cin >> t;
    int cnt = 0;
    while (t--){
   //     cin >> n >> m;
        int way = n * m;
        for (int i = 1 ; i <= n * m ; i++)
            cin >> a[i][way + 1];
        // 构建方程组
        for (int i = 1 ; i <= n ; i++){
            for (int j = 1 ; j <= m ; j++){
                int t = (i - 1) * m + j;
                for (int k = 1 ; k <= n ; k++){
                    for (int l = 1 ; l <= m ; l++){
                        int g = (k - 1) * m + l;
                        a[t][g] = b[i][j][k][l];
                    }
                }
            }
        }
        //高斯消元 含多个解
        int r , c;
        for (r = 1 , c = 1 ; r <= way && c <= way; r++ , c++){
            int p = r;
            for (int j = r + 1 ; j <= way ; j++)
                if (a[j][c] > a[p][c]) p = j;
            if (a[p][c] == 0){
                r--;
                continue;
            }
            swap(a[r] , a[p]);
            for (int j = 1 ; j <= way ; j++){
                if (r == j) continue;
                if (a[j][c] == 0) continue;
                for (int k = c ; k <= way + 1 ; k++)
                    a[j][k] ^= a[r][k];
            }
        }
        cout << "PUZZLE #" << (++cnt) << endl;
        for (int i = 1 ; i <= way ; i++){
            int x = (i - 1) / m + 1 , y = (i - 1) % m + 1;
            res[x][y] = a[i][way + 1];
        }
        for (int i = 1 ; i <= n ; i++){
            for (int j = 1 ; j <= m ; j++){
                cout << res[i][j];
                if (j == m) cout << endl;
                else cout << " ";
            }
        }
    }
    return 0;
}

类似题目:POJ1681

大意：和POJ1222一模一样的模型。求最少变成全0矩阵的步数.

思路:

求出*元之后，暴力枚举*元的所有状态，对于所有可行解，统计 1 1 1的个数，求个最小值即可.