143、最大异或对
此题不好理解的地方就是s所代表的的意思。
首先本题用静态二维数组来模拟树,son[0]代表根结点,son[0][0]与son[0][1]表示一个数用二进制表示的第一位是0或者是1,如果是0,则son[0][0] == ++idx; 表示创建了一个son[idx] 结点,他的父结点是son[0][0]存放了子结点的下标用作索引。
在insert函数中,s表示的是x这个数的二进制表示从最高位son[0][0]或son[0][1]开始 一位一位所在的索引。
如果为0则表示还没有在该位上为该值的结点,因此赋予一个下标idx表示创建结点。
在query函数中,s表示x的二进制表示在当前第i位上的数字是1或者是0。并在Trie数中一步步向下寻找。
#include <iostream>
using namespace std;
const int N = 100010,M = 3000000;
int n;
int a[N];
int son[M][2],idx;
void insert(int x){
int p = 0;
for(int i = 30;i >= 0;i--){
int &s = son[p][x >> i & 1];
if(!s) s = ++idx;
p = s;
}
}
int query(int x){
int res = 0;
int p = 0;
for(int i = 30;i >= 0;i--){
int s = x >> i & 1;
if(son[p][!s]){ // if判断成功的标志是当前位上有另一个分支,因此往另一个分支上走
res += 1 << i; // 查找的值与x在第i位上数字不同,因此异或后该位置为1
p = son[p][!s];
}
else
p = son[p][s];
}
return res;
}
int main(){
cin >> n;
for(int i = 0;i < n;i++) cin >> a[i],insert(a[i]);
int res = 0;
for(int i = 0;i < n;i++){
res = max(res,query(a[i]));
}
cout << res << endl;
return 0;
}