题解 CF1285D 【Dr. Evil Underscores】

比赛的时候看到这题，想起了上次被[这题](https://www.luogu.com.cn/problem/CF1270C)支配的恐惧，不断提醒自己绝对不能想复杂，这是CFdiv2，不会考数据结构！代码一定很短！

然后yy出分治之后以为时间复杂度是错的。。。于是就又浪费了十分钟想到了01tire的做法。

思路：首先，我们可以通过构造$X$使任意的$a_i$成为整个序列中最大的$a_i \ \text{xor}\  X$,那么我们可以尝试对于每个$a_i$都构造出满足条件的$X$，并保证$a_i \  \text{xor} \ X$最小，最后我们取所有答案的最小值即可。

那么怎么保证$a_i\ \text{xor}\ X$是序列中最大的同时尽量最小呢？假设我们处理到第j-1位，那么我们必须保证$a_i\ \text{xor}\ X$是当前最大的，而这一位，如果有前j-1位与$a_i$相同，且第j位与$a_i$不同，那么我们就需要使$a_i \ \text{xor} X$的这一位为1，否则$a_i \ \text{xor} X$就不是序列最大的了。

什么东西能满足是否存在查询前j-1位相同第j位不相同的数呢？把所有$a_i$的01trie建出来即可。

code:
```cpp
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define MN 100005
int n,a[MN],cnt,nex[MN<<5|1][2],ans[MN],X[MN];
int main(){
	scanf("%d",&n);
	cnt=1;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		int add=1;
		for(int j=30;j>=0;--j){
			bool op=(a[i]>>j)&1;
			if(!nex[add][op])nex[add][op]=++cnt;
			add=nex[add][op];
		}
	}//建tire
	int p=1;
	for(int i=1;i<=n;++i){
		int now=1;
		for(int j=30;j>=0;--j){
			int op=(a[i]>>j)&1;
			if(!nex[now][!op]){X[i]|=(((LL)op)<<j);}
			else X[i]|=(((LL)!op)<<j),ans[i]|=(1<<j);//如果有另一位，那么这一位的答案必须为1
			now=nex[now][op];
		}
		if(ans[i]<ans[p])p=i;
	}
	printf("%d\n",ans[p]);

return 0;
}
```

正在渲染内容...