F - Xor Minimization
当前没有测试数据。
F - 最小化异或运算
得分: $500$ 分
问题描述
给定一个非负整数序列 $A=(a_1,\ldots,a_N)$。
让我们对 $A$ 执行以下操作。
- 选择一个非负整数 $x$。然后，对于 $i=1, \ldots, N$，用 $a_i$ 与 $x$ 的异或运算结果取代 $a_i$ 的值。
设操作后 $A$ 中的最大值为 $M$。找到 $M$ 的最小可能值。
什么是异或运算？
非负整数 $A$ 和 $B$ 的异或运算 $A \oplus B$ 的定义如下。- 当 $A \oplus B$ 用二进制表示时，$k$-th 位（$k \geq 0$）是 $1$ 当且仅当 $A$ 和 $B$ 的 $k$-th 位上只有一个为 $1$，否则为 $0$。
约束
- $1 \leq N \leq 1.5 \times 10^5$
- $0 \leq a_i \lt 2^{30}$
- 输入中所有的值都是整数。
输入
输入的格式如下：
输出
输出答案。
3
12 18 11
16
如果我们选择 $x=2$ 进行操作，序列变为 $(12 \oplus 2,18 \oplus 2, 11 \oplus 2) = (14,16,9)$，其中最大值 $M$ 为 $16$。
我们无法使 $M$ 小于 $16$，所以这个值就是答案。
10
0 0 0 0 0 0 0 0 0 0
0
5
324097321 555675086 304655177 991244276 9980291
805306368