CF1592F1 Alice and Recoloring 1 题解
题意：
本题与 CF1592F2 的差异在于花费不同。
给定一个 \(n\) 行 \(m\) 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。
现在你可以矩阵实施以下操作：
- 使用一块钱，选定一个包含 \((1,1)\) 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。
- 使用两块钱，选定一个包含 \((n,1)\) 的子矩阵，把矩阵中的元素全部反转。
- 使用四块钱，选定一个包含 \((1,m)\) 的子矩阵，把矩阵中的元素全部反转。
- 使用三块钱，选定一个包含 \((n,m)\) 的子矩阵，把矩阵中的元素全部反转。
现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。
输入格式：
第一行两个正整数 \(n\) 和 \(m (1 \le n,m\le 500)\) ，意义如上文所述。
接下来 \(n\) 行，每行 \(m\) 个字符 W 或 B 。意义如上文所述。
输出格式：
一行一个整数，表示把初始矩阵变为目标矩阵所需的最少钱数。
先做了 F2 再做的 F1，因此本题解可能比较简陋，F2 的题解链接
首先注意到 \((n,1)\) 的操作和 \((1,m)\) 的操作都是没意义的，都可以用 \((1,1)\) 的操作替代。
于是问题转化为，只有两种操作 \((1,1)\) 和 \((n,m)\) ，价格分别是 \(1\) 和 \(3\) 元。
对 \(a_{i,j}\) 做一遍异或后缀和（ W 为 \(1\) ），也就是 \(a_{i,j} \gets a_{i, j} \oplus a_{i, j+1} \oplus a_{i+1, j} \oplus a_{i+1, j+1}\) 。
那么操作一就变成了取反 \(a_{i,j}\)，操作二变成了取反 \(a_{i,j},\,a_{i,m},\,a_{n,j},\,a_{n,m}\) 。（要是做前缀和就是反过来）
然后因为先做了 F2 所以这里即很简单了，这里操作二改 \(4\) 个点只需要 \(3\) 块，而且只需要改一次
那么我们直接贪心把这些能改的点全改了即可，最后剩下的用 \(1\) 取改。
时间复杂度 \(\mathcal{O}(nm)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(555))
char s[N][N]; int res, a[N][N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n, m; cin >> n >> m;
rep(i, 1, n) cin >> (s[i] + 1);
rep(i, 1, n) rep(j, 1, m) {
res += (a[i][j] = (s[i][j] == 'B') ^ (s[i][j + 1] == 'B')
^ (s[i + 1][j] == 'B') ^ (s[i + 1][j + 1] == 'B'));
}
for(int i = 1, ok = 0; i < n && !ok; i++)
for(int j = 1; j < m && !ok; j++)
if(a[i][j] && a[i][m] && a[n][j] && a[n][m]) { ok = true, --res; }
cout << res << '\n';
return 0;
}
