[ARC127D] Sum of Min of Xor 题解

发布时间 2023-04-07 21:58:20作者: bykem

先把 \(i\)\(j\) 的约束去掉。没有 \(\min\) 的情况是 trival 的,发现瓶颈在于如何比较两个数之间的大小。

可以发现,对两个二进制数,我们本质上是想要找到它们第一个不同的位置。于是考虑从最高位开始,将 \((a_i,b_i)\) 按最高位分组为 \((0,0),(0,1),(1,0),(1,1)\) 四组。每组内部需要继续枚举低位,因此只考虑两组之间的贡献。

可以发现,有贡献的组对如下:

  • \((0,0),(0,1)\):此时贡献为 \(a_i\oplus a_j\)
  • \((0,0),(1,0)\):此时贡献为 \(b_i\oplus b_j\)
  • \((1,1),(0,1)\):此时贡献为 \(b_i\oplus b_j\)
  • \((1,1),(1,0)\):此时贡献为 \(a_i\oplus a_j\)
  • \((0,0),(1,1)\):贡献不确定,需要继续枚举,因此我们需要将这两组并在一起向下处理。
  • \((0,1),(1,0)\):贡献不确定,需要继续枚举,因此我们需要将这两组并在一起向下处理。

直接爆算即可。