CF 1119C Ramesses and Corner Inversion

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;
}
上一篇:css样式float造成的浮动“塌陷”问题的解决办法


下一篇:Tiny4412之蜂鸣器驱动与led灯驱动