div class="part">
Problem Statement
You are given a sequence of non-negative integers $A=(a_1,\ldots,a_N)$.
Let us perform the following operation on $A$ just once.
- Choose a non-negative integer $x$. Then, for every $i=1, \ldots, N$, replace the value of $a_i$ with the bitwise XOR of $a_i$ and $x$.
Let $M$ be the maximum value in $A$ after the operation. Find the minimum possible value of $M$.
What is bitwise XOR?
The bitwise XOR of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows.- When $A \oplus B$ is written in binary, the $k$-th lowest bit ($k \geq 0$) is $1$ if exactly one of the $k$-th lowest bits of $A$ and $B$ is $1$, and $0$ otherwise.
Constraints
- $1 \leq N \leq 1.5 \times 10^5$
- $0 \leq a_i \lt 2^{30}$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $a_1$ $\ldots$ $a_N$
Output
Print the answer.
Sample Input 1
3 12 18 11
Sample Output 1
16
If we do the operation with $x=2$, the sequence becomes $(12 \oplus 2,18 \oplus 2, 11 \oplus 2) = (14,16,9)$, where the maximum value $M$ is $16$.
We cannot make $M$ smaller than $16$, so this value is the answer.
Sample Input 2
10 0 0 0 0 0 0 0 0 0 0
Sample Output 2
0
Sample Input 3
5 324097321 555675086 304655177 991244276 9980291
Sample Output 3
805306368
异或的题目，考虑01trie。不妨先把trie建出来。考虑dp。
定义 \(dp_i\) 为如果使用 trie 中点 \(i\) 的子树中的点构成的序列走。也就是如果把点 \(i\) 作为根节点，拎出来一颗 trie 树时的 答案。明显到叶子节点时，\(dp_i=0\)。
假设现在到了点 \(x\)，点 \(x\) 位于 01trie 的第 \(i\) 位。
如果他只有一个儿子有值，那么一定有办法把这一位变成0。所以可以直接继承。如果有两个儿子有值，那么这个 \(2^i\) 是逃不掉的了，所以两个儿子中选择较小的那个再加上 \(2^i\) 就行了。
但是这个 dp 中好像有个问题：我们整个序列中所有的数异或上的都是一个数，但是他当中并没有保证这个。是否会出现一个子树中某一位是1，另一个子树中某一位是0的情况呢？其实是会的，但是不影响答案。首先如果只有一个儿子，那就直接继承是没错的。但是如果有两个儿子，此时有 2^i 顶着，这比上面这种情况的影响会大很多。所以真正选择的方案按照两个儿子中 dp 值最小的那个儿子所选择的方案，大的那个不会有影响。
#include<bits/stdc++.h>
using namespace std;
const int N=1.5e5+5;
int a[N],tr[N*30][2],tag[N*30],f[N*30],n,idx(1);
void insert(int x)
{
int u=1;
for(int i=30;i>=0;i--)
{
f[u]=1<<i;
if(!tr[u][x>>i&1])
tr[u][x>>i&1]=++idx;
u=tr[u][x>>i&1];
// printf("%d\n",u);
}
tag[u]=1;
}
int dfs(int x)
{
// printf("%d\n",x);
if(tag[x])
return 0;
if(!x)
return -2000000000;
int p=dfs(tr[x][0]),q=dfs(tr[x][1]);
if(p>q)
swap(p,q);
return max(p+f[x],q);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
insert(a[i]);
}
// printf("%d %d\n",tr[0][0],tr[0][1]);
printf("%d",dfs(1));
return 0;
}