贪心、构造合集
Problem A. CF1592F1 Alice and Recoloring 1
题意：
给定一个 \(n\) 行 \(m\) 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。
现在你可以矩阵实施以下操作：
- 使用一块钱，选定一个包含 \((1,1)\) 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。
- 使用两块钱，选定一个包含 \((n,1)\) 的子矩阵，把矩阵中的元素全部反转。
- 使用四块钱，选定一个包含 \((1,m)\) 的子矩阵，把矩阵中的元素全部反转。
- 使用三块钱，选定一个包含 \((n,m)\) 的子矩阵，把矩阵中的元素全部反转。
现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。
\(1 \leq n, m \leq 500\)。
解法：
简单题。
根据对于构造与贪心的问题的一般思考方式，考虑将操作简化。容易发现以左下和右上为起点的矩形花费太大，完全没有用，但是右下角为起点的矩形可能有用。
不过进一步地，容易发现每一次对右下角矩形操作可以转为 \(4\) 次对左上矩形的操作，并且其中有一个操作是将整个矩形翻转。如果最优操作中有偶数次对右下角翻转，那么对整个矩形的翻转就被消去了，可以用左上替代。
更进一步，发现右下矩形操作次数就算是奇数，也可以将右下矩形操作变为只有 \(1\) 次。故存在方案使得只有至多一次右下矩形的操作，其余都是左上矩形的操作。
如果想到差分就做完了，想不到的可以考虑每个 \(0\) 或 \(1\) 相当于限制了这个点右下角的操作次数的奇偶性，对于每个点和右边点异或就能得到这一列的一段后缀的结果。将每一列这样的相邻不同数量求和即可。对于唯一一次右下操作，枚举位置并简单算下贡献就可以做到 \(O(n^2)\)。
Submission Link.
Problem B. CF1592F2 Alice and Recoloring 2
题意：
给定一个 \(n\) 行 \(m\) 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。
现在你可以矩阵实施以下操作：
使用一块钱，选定一个包含 \((1,1)\) 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。
使用三块钱，选定一个包含 \((n,1)\) 的子矩阵，把矩阵中的元素全部反转。
使用四块钱，选定一个包含 \((1,m)\) 的子矩阵，把矩阵中的元素全部反转。
使用两块钱，选定一个包含 \((n,m)\) 的子矩阵，把矩阵中的元素全部反转。
现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。
\(1 \leq n, m \leq 500\)。
解法：
虽然题意与 F1 不同，但是 F1 的做法能给予我们很明确的思考方向。比较容易注意到仍然只有左上和右下操作有效，但是可能存在大量右下操作都是有效的。不过还是可以从一些特殊情况入手。
首先可以发现右下操作如果顶到了左边界或上边界，那么可以直接被左上操作替代。同时可以发现不可能存在两次的右下操作互相包含且存在某条边重合。
其次，考虑差分数组 \(c_{i,j} = b_{i,j} \oplus b_{i+1,j} \oplus b_{i,j+1} \oplus b_{i+1,j+1}\)，发现左上操作是差分数组的单点取反，右下操作是将包含 \((n,m)\) 在内的四个位置单点取反。目标是将除了 \((n,m)\) 之外的点的差分值改为 \(0\)，\((n,m)\) 为 \(1\)。
进一步，考察什么样的右下操作有意义。事实上当且仅当除了 \((n,m)\) 的余下 \(3\) 个取反的位置都是 \(1\) 时才会进行操作。否则可以直接改为左上操作。
根据这样的条件，建立二分图，左侧 \(n-1\) 个点，右侧 \(m-1\) 个点。在 \((i,j)\) 进行右下操作优，就将 \((i-1,j-1)\) 连边。在二分图上跑最大匹配，剩下的还没被改的点只能用左上，直接计算即可。
如果使用朴素的最大匹配做法复杂度为 \(O(n^3)\)，使用 Dinic 可以做到 \(O(n^{2.5})\)，均可通过。
Submission Link.