3517: 翻硬币

Description

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

显然我们不会对一个硬币翻两次。。

对于一个2x2的棋盘，设\(i,j\)的颜色是\(a_{i,j}\)，翻或不翻是\(x_{i,j}\),

\[x_{1,1}\ xor\ x_{1,2}\ xor\ x_{2,1}=a_{1,1}\]

\(x_{1,2}\ xor\ x_{1,1}\ xor\ x_{2,2}=a_{1,2}\)

\(x_{2,1}\ xor\ x_{2,2}\ xor\ x_{1,1}=a_{2,1}\)

然后把三个异或以来就是

\(x_{1,1}=a_{1,1}\wedge a_{1,2}\wedge a_{2,1}\)

然后就可以计算啦

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

int n,a[1001][1001],dx[1001],dy[1001],k,ans;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%1ld",&a[i][j]);
            dx[i]^=a[i][j], dy[j]^=a[i][j];
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            ans+=a[i][j]^dx[i]^dy[j];   
    printf("%d",min(ans,n*n-ans));
}

3517: 翻硬币

原文：https://www.cnblogs.com/ZUTTER/p/10388791.html