T4

题意描述

你有 $n$ 个非负整数，第 $i$ 个数是 $a_i$。

你可以进行两种操作把这 $n$ 个数合并成一个数。

1. 选择两个数 $x,y$ 然后把它们合成一个新的数 $x\otimes y$。
2. 选择两个数 $x,y$ 然后把它们合成一个新的数 $x+y$。

其中，$\otimes$ 表示的是二进制按位与符号。选择的两个数并不需要相邻。

在 $n-1$ 步操作中你需要使用 $1$ 操作恰好 $n-k$ 次。请求出最后剩下的数的最大值。

$1\le n\le 10^6,0\le a_i<2^{30}$。

解答

注意到：一定存在一种不劣的操作方法，使得先进行 $1$ 操作，再进行 $2$ 操作。证明：

注意到，如果在算式最外层有一个形如：$(a+ b)\otimes y$ 的结构，一定可以变为 $(a\otimes b)+y$。会使得答案更大。

那么，在算式最外层一定是通过若干次 $2$ 操作合成的，既然都是 $2$ 操作，这些 $2$ 操作之前每一堆的内部都可以进行同上的调整。

转化：由于先进行 $1$ 操作，我们可以把问题转化为分成 $k$ 个集合，每一集合的按位与的和要求最大。

集合可以不在排序后的数组内连续，而且如果你的做法利用了这个假性质一定会错。

注意到：从高到低每一层（位）最优，最后就是最优的。

证明：定义一个集合在这一层显为 $x$，当它的按位与在这一层是 $x$。

考虑假设我们在第 $i$ 层可以取到更高的代价而没有取到，假设我们在这层取得了 $x$ 的代价。

考虑将这层的代价变为 $x+1$ 且使得下面层减少的量始终不超过 $2^i$。

如果此时显为 $0$ 的集合至少有两个，显为 $1$ 的集合不全是孤立的，我们把这一层显为 $0$ 的两个集合合并一下，再分裂两个显为 $1$ 的集合，此时变化量显然不超过 $2^i$。

所以最优方案中，刚才加粗的两个条件不能同时满足。

接下来我们进行细致证明。

如果一个集合里在这一位全是 $0$，则属于 A 类。

如果一个集合里在这一位全是 $1$，则属于 C 类。

否则是 B 类。

三类的数量分别记作 $a,b,c$。

如果 $a>0,b>0$，则我们可以拆开一个 B 类然后并回去 A，这样更优。

如果 $b>1$，同上，不合法。

如果 $a=0,b=1$，此时 C 类不受约束。这是一种合法的方案。

如果 $b=0$，此时 $a$ 无约束，且序列里的每一个 $1$ 都各自分一组。 这是合法的。

接下来考虑具体实现。

如果这一层要分的组数超过了 $1$ 的数量，那么根据我们上述的方案，每个 $1$ 都可以单独一组。

此时我们直接把每个 $1$ 从序列中扔掉，但是 $0$ 的分法没有确定，所以要往下找一位。

如果没有达成上述条件，既然 $1$ 不够分，则根据上述证明（以及方案）不存在两个显为 $0$ 的组，可以把所有的 $0$ 合并成一个数，然后继续考虑下一层。

最后剩下的数显然每一位至多有一个 $1$，可以简单计算。

如此我们可以直接实现按位贪心，期望得分 $100$ 分。

时间复杂度 $O(n\log V)$。完结撒花！