有一个n行n列的棋盘，每个格子上都有一个硬币，且n为偶数。每个硬币要么是正面朝上，要么是反面朝上。每次操作你可以选定一个格子(x,y)，然后将第x行和第y列的所有硬币都翻面。求将所有硬币都变成同一个面最少需要的操作数。n<=1000.
guozizheng?guozizheng! 操作次数最少,那么每个位置操作次数为0次或1次. 全变成0的方案完全取反(操作变成不操作,不操作变成操作)就得到了全变成1的方案.(影响位置(i,j)的位置有一行一列共2n-1个,为奇数个,全部取反之后异或和一定会变) x[i][j]表示第i行j列的硬币是否被操作一次(x[i]][j]=0表示没有被操作一次,x[i][j]=1表示被操作了一次).那么对于每个硬币可以列出一个异或方程.然后注意一下这些方程的特征,手动解一下.把第i行和第j列的2n-1个方程都异或起来可以求出x[i][j].
#include<cstdio> #include<algorithm> using namespace std; const int maxn=1005; int sumx[maxn],sumy[maxn]; int a[maxn][maxn]; int read(){ char ch;while(ch=getchar(),ch!='0'&&ch!='1'); return ch-'0'; } int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ a[i][j]=read(); sumx[i]^=a[i][j];sumy[j]^=a[i][j]; } } int ans=0; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) ans+=(sumx[i]^sumy[j]^a[i][j]^1); printf("%d\n",min(ans,n*n-ans)); return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7536782.html
相关资源：数据结构—成绩单生成器