题解

• 结论

  • 设数组为 $a_1,\dots,a_n$，最大值为 $M=\max(a_i)$，其二进制长度为 $L$（特别地，当 $M=0$ 时 $L=1$）。
  • 记按位与为 $A=\bigwedge_{i=1}^n a_i$，定义掩码 $mask=2^L-1$。
  • 使总和最大的最小初始 $x$ 为：

  

题目内容

小美有一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$} ，他希望构造一个非负整数 $x$ ， 满足 $x$ 的二进制位数不超过数组中最大值的二进制位数(特别的 $0$ 二进制位数为 $1$ )。

随后，可对数组 $a$ 重复进行以下操作，以使所有元素的总和最大：

• 选择一个下标 $i$ ，同时将 $a_i$ 修改为 $a_i$ $or$ $x$ ，将 $x$ 修改为 $a_i$ $and$ $x$ 。