BZOJ3517 翻硬币
题目描述
有一个 \(n\) 行 \(n\) 列的棋盘，每个格子上都有一个硬币，且 \(n\) 为偶数。每个硬币要么是正面朝上，要么是反面朝上。每次操作你可以选定一个格子 \((x,y)\)，然后将第 \(x\) 行和第 \(y\) 列的所有硬币都翻面。求将所有硬币都变成同一个面最少需要的操作数。
Solution
翻面，常见 $ trick $：将翻面转化为异或操作（因为都是进行两次相同操作等于没操作）。
令原串为 \(s\)，\(f_{x, y}\) 代表 \((x, y)\) 是否要进行操作，则有：
\[ s_{x, y} \oplus (\oplus_{i = 1}^n f_{x, i}) \oplus (\oplus_{i = 1}^n f_{i, y}) = 0 \\ \therefore s_{x, y} = (\oplus_{i = 1}^n f_{x, i}) \oplus (\oplus_{i = 1}^n f_{i, y}) \]而我们要推出 \(f_{x, y}\)，所以倒推，得：
\[ (\oplus_ {i = 1} ^ n s_{x, i}) \oplus (\oplus_{i = 1}^n s_{i, y}) \oplus s_{x, y} \\ = (\oplus_ {i = 1} ^ n [ (\oplus _ {j = 1} ^ n f_{j, i}) \oplus (\oplus _ {j = 1} ^ n f_{x, j}) \oplus f _ {x, i} ]) \\ \oplus (\oplus_ {i = 1} ^ n [ (\oplus _ {j = 1} ^ n f_{j, y}) \oplus (\oplus _ {j = 1} ^ n f_{i, j}) \oplus f _ {i, y} ]) \oplus s_{x, y} \\ = (\oplus _ {i = 1} ^ n [(\oplus _ {j = 1} ^ n f_{j, i}) \oplus (\oplus _ {j = 1} ^ n f_{x, j})]) \\ \oplus (\oplus _ {i = 1} ^ n [(\oplus _ {j = 1} ^ n f_{j, y}) \oplus (\oplus _ {j = 1} ^ n f_{i, j})]) \oplus f_{x, y} \\ = f_{x, y} \]所以 \(f\) 可以用 \(s\) 表示了，异或前缀和即可优化到 \(O(n ^ 2)\)。
Code
#include <iostream>
using namespace std;
#define Maxn 1005
#define fo(i, l, r) for(int i = l; i <= r; ++i)
int n, line[Maxn], col[Maxn], ans;
char s[Maxn][Maxn];
int main()
{
scanf("%d", &n);
fo(i, 1, n) scanf("%s", s[i] + 1);
fo(i, 1, n) fo(j, 1, n) line[i] ^= (s[i][j] - '0'), col[j] ^= (s[i][j] - '0');
fo(i, 1, n) fo(j, 1, n) ans += line[i] ^ col[j] ^ (s[i][j] - '0');
printf("%d", min(ans, n * n - ans));
return 0;
}