1 条题解

  • 1
    @ 2021-8-1 17:27:24

    观察到在纯暴力里面,栈永远仅包含 01 值,操作也全是 01 值操作,相对浪费。
    于是可以 ω\omega 个求值处一起计算;将当前状态用一个 unsigned long long 等结构绑起来。
    对每一个 ω\omega 求值块,处理出来在这个块里的所有变量在块里所含有的值,用一个类似与转置的方法,可以 O(ω2)O(\omega^2) 暴力解决。 最后,可以直接用栈模拟这一块,和暴力本质没区别。
    整体时间复杂度 O(nm/ω)O(nm/\omega)

    信息

    ID
    131
    时间
    3000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    25
    已通过
    3
    上传者