题解 P9023 [CCC2021 J5/S2] Modern Art

· · 个人记录

Statement

翻转 01 矩阵的行/列，求最终矩阵的 1 的个数。

Sol

虽然是简单的黄题，还是提供一种时间复杂度不依赖于 n,m 大小的做法。

维护被修改单数次的行。不难发现这最多只有 k 个。可以用 set 或者 unordered_set 简单维护。

同理维护被修改单数次的列。

记被修改单数次的行的个数和列的个数分别为 c',r' 。

一共有 c'\times m+r'\times n 个格子被修改成了 1。但是其中有 c'\times r' 个格子因为被修改了两次又变回来了。同时这些格子在上面也被计算了两次，简单小学容斥可以算出答案是 c'\times m+r' \times n-2\times c'\times r' 。

用 unorderedset 的复杂度是 O(k)。在 n,m 远大于 k 的时候表现优秀。

当然由于本题的 n,m 较小，用 vector 维护也很快。

Code

反正大家都会做，就放个链接罢。

vector 做法

uset 做法