[CF1592F] Alice and Recoloring

还没写完。

一道看上去不可做的题。

但是一步转化之后，分析就很有条理。

题目链接1 和 题目链接2。

题意

现在有一个 的矩阵，每一个位置是 或 ，现在可以进行若干次操作。

1. 选择一个包含 的子矩阵，将其中元素全部反转，代价为 ；

2. 选择一个包含 的子矩阵，将其中元素全部反转，代价为 ；

3. 选择一个包含 的子矩阵，将其中元素全部反转，代价为 ；

4. 选择一个包含 的子矩阵，将其中元素全部反转，代价为 ；

对于第一题，有 ，对于第二题，有 。

求将所有元素都变成 的最小代价

题解

第一题：

发现二操作和三操作都可以使用 次一操作代替，所以相当于只有一操作和四操作是有用的。

这个时候发现可能不太好做，这个时候就有一个神奇转化了。

对于 与 ，定义 。

其中对于 或 的部分，有 。

那么 全 相当于是 全 。

此时 1 操作相当于将 翻转。

4 操作相当于将 这 个格子翻转。

考虑这个时候，如果 4 操作被做了两次，那么 这个格子相当于没动，等于花费了 的代价，翻转了至多 个格子，不如直接全做 1 操作。

这告诉我们，4 操作最多被执行一次。

那么这就好做了，考虑先求出所有的 ，这样就知道了只使用 1 操作需要翻转哪些格子。

然后若存在 与 满足 ，这 个 1 操作可以放一起执行一次 4 操作，省下 的代价。

这样 F1 就做完了。代码。

---

第二题：

首先还是能发现操作二三显然没用，然后考虑还是使用上面的转化。

考虑如果有两次 4 操作在同一行，那么就相当于使用 的代价翻转了至多 个格子，也不如直接全做 1 操作。

列同理。这说明不会有 4 操作在同一行或同一列。

再来考虑，若 中有一个不是 ，那么在做了一次 4 操作之后，还得使用 次 1 操作给他翻回来，不如直接做 1 操作。

考虑在 的时候给 这个格子做一次 4 操作会带来什么影响。

会发现在 的时候会减少 的代价，在 的时候代价不变。

那么这说明，我们应该尽可能多做满足条件的 4 操作。

这就简单了，直接建二分图跑最大匹配就好了。

范围不大，跑个匈牙利就好了， 同阶的时候复杂度是 。

代码。