观察到在纯暴力里面,栈永远仅包含 01 值,操作也全是 01 值操作,相对浪费。 于是可以 ω\omegaω 个求值处一起计算;将当前状态用一个 unsigned long long 等结构绑起来。 对每一个 ω\omegaω 求值块,处理出来在这个块里的所有变量在块里所含有的值,用一个类似与转置的方法,可以 O(ω2)O(\omega^2)O(ω2) 暴力解决。 最后,可以直接用栈模拟这一块,和暴力本质没区别。 整体时间复杂度 O(nm/ω)O(nm/\omega)O(nm/ω)。
unsigned long long
注册一个 HydroOJ 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 HydroOJ 通用账户