Alice and Recoloring 1

题目描述

题目传送门

思路

没想到对矩阵的转化qwq

不妨假设 W 为 $1$，B 为 $0$。

显然操作 2、3 都可以由两次操作 1 容斥得到，而且花费更优。可以不考虑。

于是我们只需要考虑操作 1、4 的贡献。

矩阵的全部元素翻转相当于子矩阵异或 $1$。处理矩阵很麻烦，有没有办法将矩阵信息拍平到几个点上呢？

可以考虑构造 $a_{i,j} = c_{i,j} \oplus c_{i+1,j} \oplus c_{i,j + 1} \oplus c_{i + 1,j + 1}$。

这样有什么好处呢？

可以发现操作一变成了 $a_{x,y}$ 异或 $1$，操作四变成了 $a_{x-1,y-1},a_{x-1,m},a_{n,y-1},a_{n,m}$ 异或 $1$。

操作四只能选定四个为 $1$ 的点进行一次，不然会带来负影响。时间复杂度 $\mathcal{\Theta(nm)}$。

代码

#include <bits/stdc++.h>
using namespace std;
int w(char c) { return (c == 'B'); }

char c[510][510];
int n, m, a[510][510], Ans;

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> (c[i] + 1);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) 
			Ans += (a[i][j] = (w(c[i + 1][j + 1]) ^ w(c[i + 1][j]) ^ w(c[i][j + 1]) ^ w(c[i][j])));
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++)
			if (a[i - 1][j - 1] && a[i - 1][m] && a[n][j - 1] && a[n][m]) {
				Ans--;
				goto End;
			}
	End:;
	cout << Ans << endl;
	return 0;
}