526互联

AtCoder Regular Contest 122 D XOR Game

发布时间 2023-05-01 22:27:05作者: zltzlt

洛谷传送门

AtCoder 传送门

从高到低按位考虑。

设当前位有 \(k\) 个 \(1\)。

  • 如果 \(k \bmod 2 = 0\)，这意味着 Alice 如果选了一个数，Bob 可以选相同的数。发现可以分成 \((0,0),(1,1)\) 两组，递归下去即可。
  • 如果 \(k \bmod 2 = 1\)，意味着答案这一位一定是 \(1\)（因为无论如何都不能消除贡献）。此时 Bob 可以做到有且仅有一对数异或和在这一位是 \(1\)，于是我们需要查两两异或和最小值，这个随便 01Trie 做一下即可。

递归复杂度 \(O(n \log V)\)，01Trie 复杂度 \(O(n \log V)\)，总时间复杂度 \(O(n \log V)\)。