F. Unusual Matrix 题解(思维)

题目链接

题目大意

给你两个01n*n矩阵(n<=1e3) a,b

你可以对a进行任意横和列的异或操作

即可以对a的任意行和任意列进行整体对1异或操作

判断是否可以将a矩阵变成b矩阵

题目思路

其实很简单。。。

很明显，操作的顺序不会影响最终的结果，而且多次同一个操作也没有意义(通过xor的属性)

那么第一行可能0次或者1次操作

那么通过第一行的操作以及第一行的元素则可以确定所有列的操作

然后用第2到第n行的元素判断是否可以满足即可

操作后行的元素只能全部相反或者全部相同才满足

代码

#include<bits/stdc++.h>
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e3+5,inf=0x3f3f3f3f,mod=1e9+7;
const int eps=1e-6;
int n;
int a[maxn][maxn],b[maxn][maxn];
int temp[maxn][maxn];
int c[maxn];
char ch;
bool check(){
    for(int i=2;i<=n;i++){
        int sum=0;
        for(int j=1;j<=n;j++){
            temp[i][j]=(a[i][j]^c[j]^b[i][j]);
            sum+=temp[i][j];
        }
        if(sum!=0&&sum!=n) return 0; //只有这一行全部相同或全部不同才满足
    }
    return 1;
}
int main(){
    int _; scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf(" %c",&ch);
                a[i][j]=ch-'0';
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf(" %c",&ch);
                b[i][j]=ch-'0';
            }
        }
        for(int j=1;j<=n;j++){ //第一行没变
            if(a[1][j]!=b[1][j]){
                c[j]=1;
            }else{
                c[j]=0;
            }
        }
        bool flag=0;
        if(check()){
            flag=1;
        }
        for(int j=1;j<=n;j++){ //第一行变了
            c[j]=!c[j];
        }
        if(check()){
            flag=1;
        }
        printf(flag?"YES
":"NO
");
    }
    return 0;
}