欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-12 14:10:56
...

题目大意:

给你一个 5 ∗ 6 5 * 6 56大小的二维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=010111010

那么 L → L ⊕ A 2 , 2 L \rightarrow L \oplus A_{2,2} LLA2,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,1A1,1)...(Xn,mAn,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,1A1,1)...(Xn,mAn,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,1A1,1[1][1]X1,2A1,2[1][1]...Xn,mAn,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,1A1,1[1][2]X1,2A1,2[1][2]...Xn,mAn,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,1A1,1[n][m]X1,2A1,2[n][m]...Xn,mAn,m[n][m]=L[n][m]

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

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

注意点:
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的个数,求个最小值即可.

相关标签: 算法 线性代数