【BZOJ 3517】翻硬币

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3517
神犇题解Ⅰ:http://blog.csdn.net/lych_cys/article/details/50363106
神犇题解Ⅱ:http://foreseeable97.logdown.com/posts/193171-bzoj3517-coins

解题报告

一道非常妙妙的题目啊!虽然没做出来 QwQ

我们先来明确两个结论:
1. 首先一个格子要么被翻一次,要么不被翻
2. 其次全部变白和全部变黑是互逆的,所以求出一个可以推出另一个。所以我们只考虑求全部变白的情况

我们考虑设$b_{i,j}$表示最终对没对$(i,j)$这个格子进行操作
于是我们可以得到$n^2$个方程,因为只有$n^2$个变量
所以我们可以用高斯消元在$O(n^3)$的时间复杂度内求解

但我我们发现题目中提到的$n$为偶数这个条件并没有用到
现在考虑优化高斯消元:

设$a_{i,j}$为这个格子的原始状态
设$xb_i$表示第$i$行所有$b_{i,j}$异或起来,$xa_i$表示第$i$行所有$a_{i,j}$异或起来
设$yb_i$表示第$i$列所有$b_{i,j}$异或起来,$ya_i$表示第$i$列所有$a_{i,j}$异或起来
于是我们可以得到$b_{i,j} \oplus xb_j \oplus yb_i = a_{i,j}$,设为一号方程
考虑我们求$b_{i,j}$,那么我们把所有第$j$行和第$i$列的方格对应的一号方程异或起来
之后我们发现因为$n$为偶数,所以等式变为$b_{i,j}=ya_i \oplus xa_j \oplus a_{i,j}$

然后我们惊讶地发现问题已经解决了?
第一次手动解异或方程组,感觉非常玄妙啊!

Code

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

const int N = 1009;

int n,ans,x[N],y[N],a[N][N];
char pat[N]; 

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main() {
	n = read();
	for (int j=1;j<=n;j++) {
		scanf("%s",pat+1);
		for (int i=1;i<=n;i++) {
			a[i][j] = pat[i] - '0';
			x[i] ^= a[i][j];
			y[j] ^= a[i][j];
		}
	}
	for (int j=1;j<=n;j++) {
		for (int i=1;i<=n;i++) {
			ans += x[i] ^ y[j] ^ a[i][j];	
		}
	} 
	printf("%d\n",min(ans, n * n - ans));
	return 0;
}