题意

给定 $n$ 个二进制数，两个人轮流操作每次选择一个数，获得这个数最低位的分数，并删除个位。双方目标均为最大化自己的分数，求最优策略下，双方得分之差。

数据范围：$1 \leq n \leq 5 \times 10^4$，$1 \leq a_i < 2^{63}$。

题解

容易把二进制数转化为栈的形式。考虑当所有栈从栈底往栈顶都递增的情形：此时双方最优策略总是取当前所有数最大的。

接下来考虑若存在相邻两项从上往下为 $x, y$ 并且 $x < y$ 时如何处理。此时若一方取走 $x$ 是最优操作，那么另一方接着取走 $y$ 也是最优操作。这个操作对先手的分数影响是负数，所以如果先手这样操作，下一步一定会取走更靠底的数 $z$。于是我们不妨让这三个数捆绑成一个数 $x - y + z$。如果此处是栈底即 $z$ 不存在，那么这样的操作一定在最后执行。

于是对于每个二进制数，都从高位往低位不断插入栈中并尝试合并即可，最后对剩余部分排序并贪心选取，再加上所有已经确定最后执行的操作的贡献。总时间复杂度为 $\mathcal{O}(n \log a_i)$。