https://codeforces.com/problemset/problem/1119/C
题目
给两个矩阵,只能选宽和高大于等于2的子矩阵左上、左下、右上、右下四点翻转(1->0,0->1)
问能否经过一些操作将A翻转到B
题解
能当且仅当每行和每列不同的数量都为偶数。
必要性:一次翻转不改变奇偶性,所以必要性成立。
充分性:可以每次进行(0,0,x,y)的操作,将除了第一行和第一列的所有不同翻转为相同,因为是不同的数量是偶数,所以第一行和第一列也相同。(把不同看成1,相同看成0)
但是想不到啊……高中学的太差了
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<iomanip> #define REP(r,x,y) for(register int r=(x); r<(y); r++)
#define REPE(r,x,y) for(register int r=(x); r<=(y); r++)
#ifdef sahdsg
#define DBG(...) printf(__VA_ARGS__)
#else
#define DBG(...) (void)0
#endif using namespace std;
typedef long long LL;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii; char ch; int f;
template <class T>
inline void read(T &x) {
x=0; f=1; do ch=getchar(); while(!isdigit(ch) && ch!='-');
if(ch=='-') ch=getchar(),f=-1; while(isdigit(ch)) {x=x*10+ch-'0';
ch=getchar();} x*=f;
} #define MAXN 507
int h[MAXN], l[MAXN];
int arr[MAXN][MAXN]; int main() {
int a,b; read(a), read(b);
REP(i,0,a) REP(j,0,b){
read(arr[i][j]);
}
REP(i,0,a) REP(j,0,b){
int t; read(t);
arr[i][j]^=t;
}
REP(i,0,a) REP(j,0,b) {
h[i]+=arr[i][j];
l[j]+=arr[i][j];
} REP(i,0,a)if(h[i]&1) {puts("no"); return 0;}
REP(j,0,b)if(l[j]&1) {puts("no"); return 0;}
puts("yes");
return 0;
}