【题解】CF1592F1 Alice and Recoloring 1

· · 题解

题目传送门

超级妙妙题！

题意：

给定一个 n \times m 的矩阵，初始时所有格子都是白色，可以进行以下四种操作：

1、翻转一个以 (1,1) 为左上角的任意子矩阵的所有颜色，代价为 1；

2、翻转一个以 (n,1) 为左下角的任意子矩阵的所有颜色，代价为 2；

3、翻转一个以 (1,m) 为右上角的任意子矩阵的所有颜色，代价为 4；

4、翻转一个以 (n,m) 为右下角的任意子矩阵的所有颜色，代价为 3。

求将初始局面变为给定局面花费代价的最小值。

首先只有黑白两种颜色，所以将一个格子翻转偶数次，相当于没有翻转。

其次，将初始局面变为给定局面，等价于将给定局面变为初始局面。因此问题可以转化成给定一个局面，要将这个局面全部变为白色格子所花费的最小代价。

发现这四种操作好像比较对称，考虑进行一些转化。

对于操作 2，翻转一个以 (n,1) 为左下角，(x,y) 为右上角的矩阵，可以转化为使用两次操作 1，第一次翻转以 (1,1) 为左上角，(n,y) 为右下角的矩形，第二次翻转以 (1,1) 为左上角，(x-1,y) 为右下角的矩形。

显然这两种操作完全等价，花费的代价也相同。因此，操作 2 没有任何意义。

类似地，对于操作 3，翻转一个以 (1,m) 为右上角，(x,y) 为左下角的矩阵，可以转化为使用两次操作 1，第一次翻转以 (1,1) 为左上角，(x,m) 为右下角的矩形，第二次翻转以 (1,1) 为左上角，(x,y-1) 为右下角的矩形。

这两种操作也是完全等价的，但是两次操作 1 只需要花费 2 代价，因此操作 3 也没有意义。

容易知道操作 4 无法转化为使用不超过三次的操作 1，因此操作 4 是有意义的。

于是证明了只有操作 1 和操作 4 有意义。下面考虑如何操作。

显然矩阵修改不好维护且十分麻烦，最好将其转化为单点修改。

可以对原矩阵 c 进行一个巧妙的转化：令白色格子为 0，黑色格子为 1。设 a_{i,j} 代表 c_{i,j} \oplus c_{i+1,j} \oplus c_{i,j+1} \oplus c_{i+1,j+1} 的结果。

容易知道，将原局面全部变成白色格子的充要条件为对于任意 1 \le i,j \le n,a_{i,j}=0。于是问题转化为将所有 a_{i,j} 变为 0 的最小方案。

考虑对于操作 1，翻转一个以 (1,1) 为左上角，(x,y) 为右下角的矩形等价于只翻转 a_{x,y}。

对于操作 4，翻转一个以 (x,y) 为左下角，(n,m) 为右下角的矩阵，等价于只翻转 a_{x-1,y-1},a_{x-1,m},a_{n,y-1},a_{n,m}。

这两个结论可以自行画图证明，这里略去。

这样操作 1 就是翻转一个点，代价为 1，操作 4 就是翻转四个点，代价为 3。

看起来操作 4 好像更优。但是操作 4 能用必须满足两个条件：1、a_{x-1,y-1},a_{x-1,m},a_{n,y-1},a_{n,m} 均为 1（翻转 a_{i,j}=0 的点会带来负收益）；2、只能进行一次（因为多次进行操作 4 会不断翻转 a_{n,m}，实际上最多翻转 3 个有效点）

所以最多进行一次操作 4，剩下的点都用操作 1 完成。

于是判断一下能否进行操作 4 并统计一下需要翻转的 a_{i,j} 的个数即可。

时间复杂度 O(nm)。