题解：CF321D Ciel and Flipboard

· · 题解

CF321D Ciel and Flipboard

这道题被搞到模拟赛里去了，我显然没做出来。我一直在考虑的都是贪心策略或者动态规划，但是知道了正确解法后，再看 n\leq 33 的数据范围，才觉自己的想法很可笑。

先说解法。既然数据范围小，但又不是那么小，那一定是和枚举有关，但又不用全枚举。而减少枚举次数就要看题中的特殊性质。数据范围是 1000 似乎并没有什么用处，而 m=\frac{n+1}2 以及 n 为奇数则显得尤为特殊。m=\frac{n+1}2 刚好比 n 的一半大一些。不难注意到，如果矩阵覆盖到了第 i 行，则 a_{i, m} 一定会被覆盖到。进一步，a_{i, j}, a_{i, j+m}(j<m) 中有且仅有一个位置被该矩阵覆盖到。设 vis_{i, j} 表示 a_{i, j} 是否取反，则 vis_{i, j}\oplus vis_{i, m}\oplus vis_{i, j+m}=0(j<m)。同理 vis_{i, j}\oplus vis_{m, j} \oplus vis_{i+m, j}=0(j<m)。这说明，如果知道了前 m 行、前 m 列是否反转，就可以知道整个矩阵的每个位置是否反转，则有 2^{m^2} 种情况，这与直接枚举是否反转每个矩阵的情况总数相同，说明只要满足以上两个式子的矩阵都是合法的矩阵。观察这个式子，在知道了第 m 行、第 m 列的所有 vis 值的情况下，被第 m 行、m 列所分成的四个区块中一个块内相邻的两个位置是没有关系的，每一个位置只和与其坐标相差 m 的位置有关，所以只要把每个 (i, j)(i, j<m) 和 (i, j+m), (i+m, j), (i+m, j+m) 放一起计算贡献，其余都可以分开来。因此可以考虑令第一个式子中 i=m，则有 vis_{m, j}\oplus vis_{m, m}\oplus vis_{m, j+m}=0。此时去枚举第 m 行的前 1 至 m 个位置的 vis 值，就可以知道第 m 行的全部 vis 值。然后再观察第 m 列，如果知道了第 vis_{i, m}(i<m)，就可以由 vis_{i, m}\oplus vis_{m, m}\oplus vis_{i+m, m}=0 知道 vis_{i+m, m} 的值。接着，对于第 i 行的第 j(j<m) 列，如果知道其 vis 值，就容易知道 vis_{i+m, j}, vis_{i, j+m}, vis_{i+m, j+m} 的值。则在 O(2^m) 枚举完第 m 行的前 m 个位置，计算出整个第 m 行后，就可以分别做每一行 i(i<m)，枚举 vis_{i, m}，再对于该行每一列 j(j<m)，分别枚举 vis_{i, j}，就知道 vis_{i+m, j}, vis_{i, j+m}, vis_{i+m, j+m}，一起计算 a_{i, j}, a_{i+m, j}, a_{i, j+m}, a_{i+m, j+m} 的贡献，把枚举出每一组 vis 的贡献计算出后求最大，然后累加起来即可。这样子是 O(n^2) 的。因此总复杂度 O(2^mn^2)。具体实现见代码。

最后讲讲做完题后的思考。对于我最初的想法，显然是不现实的，应当尽早排除。而这题的教训就是在暴力枚举前务必观察性质，有些部分可以独立枚举的就分开来，于是大大降低了复杂度。