1 条题解
-
0
题目分析
20 分
暴力枚举每一行翻不翻转,然后计算答案即可,时间复杂度 。
40 分
注意到如果钦定 这个位置为 ,那么所有行的翻转情况就固定了!
这告诉我们什么呢?可以直接枚举钦定为 的位置,然后确定所有行的翻转情况并计算答案。
枚举的位置数是 的,每次计算答案是 的,于是复杂度变成了 。
60 分
考虑优化上面的做法,可以发现每次重新计算答案将整个矩阵扫一遍是非常愚蠢的,将翻转情况与上次不同的行重新拿出来更新一下就行。时间复杂度 。
80 分
计算哪些列只有一个 的过程可以使用 bitset 优化,时间复杂度 。
正解
真的有必要枚举位置后每次都去算一遍答案吗?
考虑如果 两个位置能够同时为 ,那么两个位置所对应的行的翻转情况一定是一样的!
于是考虑对每个位置所对应的行的翻转情况进行 hash,一种行的翻转情况对应 hash 值计算方式如下:,其中 表示第 行是否翻转, 为取的一个大质数。将所有的 hash 值丢进一个 map 里,相同值个数最多的就是答案。
时间复杂度 。
- 1
信息
- ID
- 63
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者