题解：P10635 BZOJ3517 翻硬币

· · 题解

写在前面：我不太会写题解，写出来的东西都是一坨一坨的，但是已经尽量清晰的描述了，请谅解。

考虑如何使用一些操作来只翻转一位。

当我们轮流对 (x_0,i) 和 (i,y_0) 进行操作之后（(x_0,y_0) 只操作一次）：

  1. 对于 x\neq x_0 且 y\neq y_0 的 (x,y)，它仅会被 (x,y_0) 和 (x_0,y) 操作到，操作两次相当于没变；
  2. 对于 x=x_0 和 y=y_0 只有一个满足的 (x,y)，它会被所有 (x_0,i) 或所有 (i,y_0) 操作到，而 n 为偶数，所以也不变；
  3. 对于 x=x_0 且 y=y_0 的 (x,y)，它会被每一次操作影响到，总共 2n-1 次，为奇数，所以会变化。

所以，我们发现这样操作之后，我们能够仅翻转 (x_0,y_0)。

显然的，我们能够通过多次进行这样的轮流操作来翻转任意格子。如果某一个格子操作了两次则相当于没有操作，这样我们可以把每个格子上进行的操作次数限制成 0 或 1。

于是，操作后的翻转情况（格子的被操作情况）有 2^{n^2} 种，每个格子的操作情况也有 2^{n^2} 种，而且每个翻转情况都有对应的操作情况，而操作情况能唯一对应翻转情况。这些足以说明每一个翻转情况对应的操作情况也是唯一的。因此，这个操作方式去掉无用操作后一定是最优解。

首先考虑怎么把 1 全改成 0。我们给每行和每列打一个标记代表要对其整行或整列操作的次数，对于每个 1 的位置 (x,y)，我们让第 x 行和第 y 列的标记加一。之后我们枚举每一个位置，其需要操作的次数是其自身是否需要操作（即自身是否为 1）加上所在行与所在列的次数之和。如果这个和是奇数就需要操作它。

而从 0 全改成 1 的方法就很简单：因为 n 是偶数，所以每行或每列中 0 和 1 的数量奇偶性相同，也就是说行标记和列标记对这两种方案的影响是一样的。而因为从 0 改成 1 的数量与 1 改成 0 的数量和为 n^2，所以同时影响这两种方案之后（因为对于一个方格，两种方案同时翻转之后的操作次数之和还是 1）和不变，仍然为 n^2。因此，n^2 减去 1 全改成 0 的次数就是 0 全改成 1 的次数。

实现很简单。

cin>>n;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
    cin>>ch[i][j];
    if(ch[i][j]=='1')++r[i],++c[j];
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
    ans+=(ch[i][j]+r[i]+c[j])&1;
}
cout<<min(ans,n*n-ans)<<"\n";