最后翻为0和1本质相同，只考虑一种。显然每个硬币最多翻一次。考虑设xi,j表示i,j位置的硬币是否翻，那么很容易就可以列出异或方程组。变量和方程都有n2个，那么解是唯一的，就不用考虑怎样最小化了。然而暴力高斯消元肯定是不行的。
考虑将所有关于xi,k和xk,j的方程叠加，由于n是偶数，可以得到xi,j=ai,k^ak,j^ai,j (k=1~n)。于是就解出来了。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1;c=getchar();} while (c>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 1010 int n,a[N][N],s[2][N],ans; int main() { #ifndef ONLINE_JUDGE freopen("bzoj3517.in","r",stdin); freopen("bzoj3517.out","w",stdout); const char LL[]="%I64d\n"; #else const char LL[]="%lld\n"; #endif n=read(); for (int i=1;i<=n;i++) { char c=getchar(); while (c!=‘0‘&&c!=‘1‘) c=getchar(); for (int j=1;j<=n;j++) a[i][j]=c^48,c=getchar(); } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) s[0][i]^=a[i][j],s[1][j]^=a[i][j]; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) ans+=s[0][i]^s[1][j]^a[i][j]; cout<<min(ans,n*n-ans); return 0; }
原文：https://www.cnblogs.com/Gloid/p/9697180.html