洛谷 P3164 [CQOI2014]和谐矩阵

题目链接

高斯消元求解异或方程组

若(i)号灯影响(j)号灯，(g_{j,i} = 1)

消去其它行，用异或消去。 注意循环里的if语句不要缺少。

计算答案时记得跳过自由元。

#include<bits/stdc++.h>
using namespace std;

int n,m;
int g[2005][2005];
int ans[2005];

int main(){
    scanf("%d%d",&n,&m);
    
    for(int i = 0; i < n; ++ i) 
    for(int j = 1; j <= m; ++ j){
        int id = i * m + j, ps;
        ps = i * m + j; g[ps][id] = 1;
        if(i > 0) ps = (i - 1) * m + j, g[ps][id] = 1;
        if(i < n - 1) ps = (i + 1) * m + j, g[ps][id] = 1;
        if(j > 1) ps = i * m + j - 1, g[ps][id] = 1;
        if(j < m) ps = i * m + j + 1, g[ps][id] = 1;    
    }
    
    int N = n * m;
    int now = 1;
    
    for(int i = 1; i <= N; ++ i){
        int ps = now;
        for(int j = now + 1; j <= N; ++ j){
            if(g[j][i] > g[ps][i]) ps = j;
        } 
        if(g[ps][i] == 0) continue;
        if(ps != now){
            for(int j = 1; j <= N + 1; ++ j)
            swap(g[ps][j],g[now][j]);
        }
        
        for(int j = now + 1; j <= N; ++ j){
            if(g[j][i] == 0) continue;
            for(int k = 1; k <= N + 1; ++ k) 
            g[j][k] ^= g[now][k];
        }
        
        ++ now;
    }
    
    for(int i = 1; i <= N; ++ i) ans[i] = 1;
    
    for(int i = now - 1; i >= 1; -- i){
        int ps = -1;
        for(int j = 1; j <= N; ++ j)
        if(g[i][j] == 1) { ps = j; break; }
        for(int j = N; j > ps; -- j){
            g[i][N + 1] ^= (g[i][j] & ans[j]);
        } 
        ans[ps] = g[i][N + 1];
    }
    
    for(int i = 0; i < n; ++ i){
        for(int j = 1; j <= m; ++ j)
        printf("%d ",ans[i * m + j]);
        puts("");
    }
    
    return 0;
}