1 条题解

  • 0
    @ 2026-11-15 13:29:03

    题目分析

    20 分

    暴力枚举每一行翻不翻转,然后计算答案即可,时间复杂度 O(m22n)\mathcal{O}(m^22^n)。

    40 分

    注意到如果钦定 (i,j)(i,j) 这个位置为 11,那么所有行的翻转情况就固定了!

    这告诉我们什么呢?可以直接枚举钦定为 11 的位置,然后确定所有行的翻转情况并计算答案。

    枚举的位置数是 O(nm)\mathcal{O}(nm) 的,每次计算答案是 O(nm)\mathcal{O}(nm) 的,于是复杂度变成了 O(n2m2)\mathcal{O}(n^2m^2)。

    60 分

    考虑优化上面的做法,可以发现每次重新计算答案将整个矩阵扫一遍是非常愚蠢的,将翻转情况与上次不同的行重新拿出来更新一下就行。时间复杂度 O(nmmax⁡(n,m))\mathcal{O}(nm\max(n,m))。

    80 分

    计算哪些列只有一个 11 的过程可以使用 bitset 优化,时间复杂度 O(nmmax⁡(n,m)w)\mathcal{O}(\frac{nm\max(n,m)}{w})。

    正解

    真的有必要枚举位置后每次都去算一遍答案吗?

    考虑如果 (i,j),(k,l) (j≠l)(i,j),(k,l)\ (j\ne l) 两个位置能够同时为 11,那么两个位置所对应的行的翻转情况一定是一样的!

    于是考虑对每个位置所对应的行的翻转情况进行 hash,一种行的翻转情况对应 hash 值计算方式如下:∑i=1nCipi\sum_{i=1}^n C_ip^i,其中 CiC_i 表示第 ii 行是否翻转,pp 为取的一个大质数。将所有的 hash 值丢进一个 map 里,相同值个数最多的就是答案。

    时间复杂度 O(nm)\mathcal{O}(nm)。

    • 1

    信息

    ID
    63
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者