这道题真是令人长知识
居然异或想到用Trie树
异或的时候,我们沿着树枝走,
没有别的分叉的话,没有办法,只能沿着这一条走,
如果有分叉的话,就尽量沿着与自己这一二进制位上的数相反的分支走,
这样走到头,就出来一对异或值。
然后把现在处理的这个数加到trie树上去
这样最后所有的异或值比出一个最大的来就是答案
这种不总寻常路的异或方式着实让人拍案叫绝
操作顺序问题:
1.边插入边查询,不需要先全部插入再查找
因为a^b和b^a一样,如果先全部插入的话会两个都算
当然也不是不行,就是有点慢
2.先插入再查询
这样一开始没有数的时候,我们就不需要特判空trie树了
好像表述得不是很清楚
但是这个玩意插入图片好麻烦
所以没有看懂的同学建议去听听yxc老师的课叭
(真的不是打广告他讲的真的好发自内心的安利)
//来自算法基础课
CODE
#include<bits/stdc++.h>
#define R register int
#define read(x) scanf("%d",&x)
using namespace std;
const int N = 1e5+5;
const int M = 31;
int n,idx,son[M*N][2];
int a[N],ans;
void build(int a) {
int s = 0;
for(register int i=30; i>=0; i--){
int e = (a>>i) & 1;
if(!son[s][e]) son[s][e] = ++idx;
s = son[s][e];
}
}
int query(int a) {
int s = 0, res = 0;
for(register int i=30; i>=0; i--) {
int e = (a>>i) & 1;
if(son[s][!e]) {//尽量往与自己相反的方向走,因此判断对面方向是否存在
res = res*2 + !e;//先右移一位,再加上当前位,得出的就是异或值
s = son[s][!e];
}
else {
res = res*2 + e;
s = son[s][e];
}
}
return res;
}
int main(){
read(n);
for(register int i=0; i<n; i++) {
read(a[i]);
build(a[i]);
int t = query(a[i]);//t就是找到得可以与a[i]异或起来最大的数
ans = max(ans,a[i]^t);
}
printf("%d\n",ans);
return 0;
}