相关链接
题目传送门: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; }
好文章!666,学习了
fantastic post.Never knew this, thanks for letting me know.
Respect to post author, some great entropy.