你是一名c++老师请教我21世纪许多人得了一种奇怪的病：起床困难综合症其临床表现为：起床难起床后精神不佳。作为一名青春阳光好少年atm一直坚持与起床困难综合症作斗争。通过研究相关文献他找到了该病的发病原因： 在深邃的太平洋海底中出现了一条名为drd的巨龙它掌握着睡眠之精髓能随意延长大家的睡眠时间。正是由于drd的活动起床困难综合症愈演愈烈 以惊人的速度在世界上传播。为了彻底消灭这种病atm决定前往

算法

(搜索) $O(2^m\times n)$

• 基于搜索的暴力枚举，每次枚举 $0 \sim m$ 中的整数 $x$，并计算通过所有门后的攻击力，最终取最大值。
• 时间复杂度 $O(2^m\times n)$，可以通过此题。

时间复杂度

参考文献

Python3 代码

C++ 代码

算法

(二分答案) $O(32\times n\times \log_{2}{m})$

• 基于二分答案的思想，我们可以枚举通过所有门后的攻击力 $y$，然后检查是否有 $0 \sim m$ 中的整数 $x$，使得通过所有门后的攻击力等于 $y$。
• 有一个性质：任意两个整数 $x,y$，都可以表示为 $x\oplus y,y\oplus (x\oplus y)$ 中的一个。
• 我们可以枚举 $0 \sim 31$ 中的整数 $k$，然后将所有参数 $t$ 二进制下第 $k$ 位为 $1$ 的门分为一组，第 $k$ 位为 $0$ 的门分为一组。
• 对于当前枚举的 $y$，我们依次枚举每一组门中的元素，对其进行运算，得到一个新的数 $z$。然后我们在另一组门中查找是否存在一个元素 $t$，使得 $y=(t\texttt{ op }z)$，如果存在，那么此时的 $y$ 就是可行的。
• 时间复杂度 $O(32\times n\times \log_{2}{m})$，可以通过此题。

时间复杂度

参考文献

C++ 代