P10635 BZOJ3517 翻硬币 题解

· · 题解

首先，大家要知道一个常识：硬币翻两次等于没翻，故题目简单起来了，然后分开统计全转 0 和全转 1 操作数，小的输出。

具体流程：输入时分别统计 0 和 1，若是想要的 0/1，则 a_{i,j} 赋值 1，自身行列各加 1,（因为每次翻 (i,j) 都会影响第 i 行和第 j 列，所以 h_{i}，z_{j} 分别 +1），如果是 1，则同理。

输出：统计每个位置需要翻几次才能达到想要的 0/1，每次统计 a_{i,j}+h_{i}+z_{j}，因为翻两次等于没翻故再取余 2，sum 累加这个值，最后比较 sum0，sum1。收工。

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,h1[N],z1[N],a1[N][N],sum1,h0[N],z0[N],a0[N][N],sum0;//后面带1的：全转1的行数，列数，以及本体需要的0/1次，后面带0的同理 
char c;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>c;
            if(c=='0')a1[i][j]=1,h1[i]++,z1[j]++;//全转1
            else a0[i][j]=1,h0[i]++,z0[j]++;//全转0 
        }   
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)sum1+=(a1[i][j]+h1[i]+z1[j])%2,sum0+=(a0[i][j]+h0[i]+z0[j])%2;//统计需要次数，因翻两次等于没翻，故取余2
    cout<<min(sum0,sum1);//取最小 
    return 0;
}