[bzoj3517]翻硬币——异或方程组求解

题目大意：

有一个n行n列的棋盘，每个格子上都有一个硬币，且n为偶数。每个硬币要么是正面朝上，要么是反面朝上。每次操作你可以选定一个格子(x,y)，然后将第x行和第y列的所有硬币都翻面。求将所有硬币都变成同一个面最少需要的操作数。

思路：

看似很套路的题目，感觉在atcoder可能出现过。 容易得到每个点至多只会被翻转一次，我们设 x[i][j] x [ i ] [ j ] 为 (i,j) ( i , j ) 翻转过的次数。 首先考虑把所有的1都变成0，那么有 a[i][j]=x[i][1]⊕x[i][2]⊕...⊕x[i][n]⊕x[1][j]⊕x[2][j]...⊕x[n][j] a [ i ] [ j ] = x [ i ] [ 1 ] ⊕ x [ i ] [ 2 ] ⊕ . . . ⊕ x [ i ] [ n ] ⊕ x [ 1 ] [ j ] ⊕ x [ 2 ] [ j ] . . . ⊕ x [ n ] [ j ] 考虑怎么解这个方程，我们要只有一个 x[i][j] x [ i ] [ j ] ,可以把所有与 i,j i , j 有关的全部异或合起来然后发现最后的答案就是 x[i][j]=a[i][1]⊕a[i][2]⊕...⊕a[i][n]⊕a[1][j]⊕a[2][j]...⊕a[n][j] x [ i ] [ j ] = a [ i ] [ 1 ] ⊕ a [ i ] [ 2 ] ⊕ . . . ⊕ a [ i ] [ n ] ⊕ a [ 1 ] [ j ] ⊕ a [ 2 ] [ j ] . . . ⊕ a [ n ] [ j ] (因为n为偶数，所以最后全部抵消了，画个图好理解些。)

/*============================= * Author : ylsoi * Problem : bzoj3517 * Algorithm : XOR ??? * Time : 2018.6.9 * ==========================*/ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<climits> using namespace std; void File(){ freopen("bzoj3517.in","r",stdin); freopen("bzoj3517.out","w",stdout); } #define REP(i,a,b) for(register int i=a;i<=b;++i) #define DREP(i,a,b) for(register int i=a;i>=b;--i) #define MREP(i,x) for(register int i=beg[x];i;i=E[i].last) #define mem(a) memset(a,0,sizeof(a)) #define ll long long #define inf INT_MAX const int maxn=1000+10; int n,a[maxn][maxn],sum[maxn][2],ans; int main(){ File(); scanf("%d",&n); REP(i,1,n)REP(j,1,n) scanf("",&a[i][j]); REP(i,1,n)REP(j,1,n){ sum[i][0]=sum[i][0]^a[i][j]; sum[j][1]=sum[j][1]^a[i][j]; } REP(i,1,n)REP(j,1,n) ans+=sum[i][0]^sum[j][1]^a[i][j]; ans=min(ans,n*n-ans); printf("%d\n",ans); return 0; }