acwing 143.最大异或对（字典树）

题目传送门：?143. 最大异或对

在给定的?N?个整数?A1，A2……AN?中选出两个进行?xor（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数?N。

第二行输入?N?个整数?A1～AN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤1e5,
0≤Ai<2^31

输入样例：

3
1 2 3

输出样例：

3

?试题解析

字典树存储+查询，

思路：将每个数以二进制的方式存入字典树
? ? ? ? ? ?查找的时候从最高位找与当前数据当前位数不同的位
? ? ? ? ? ?若没有不同的位，则选取相同的位，并继续下一位的选取

?代码如下：

#include<iostream>
using namespace std;
const int N = 100010, M = 31 * N;
// M代表一个数字串二进制可以到多长
int arr[N], son[M][2];
int idx;
void insert(int x) {
	int p = 0; //类似指针，指向当前节点
	for (int i = 30; i >= 0; i --) {
		int u = x >> i & 1;// 取x的最高位二进制数
		if (!son[p][u]) son[p][u] = ++idx; //若该节点不存在，创建节点，值为下一个位置
		p = son[p][u];//使p指向下一个节点
	}
}
int query(int x) {
	int p = 0, res = 0;
	for (int i = 30; i >= 0; i --) {
		int u = x >> i & 1;
		if (son[p][!u]) { //如果当前层有对应的不相同的数
			p = son[p][!u];
			res = res * 2 + !u;
		} else {
			p = son[p][u];
			res = res * 2 + u;
		}
	}
	return res;
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i ++) {
		scanf("%d", &arr[i]);
	}
	int res = 0;
	for (int i = 0; i < n; i ++) {
		insert(arr[i]);
		int t = query(arr[i]);
		res = max(res, t ^ arr[i]);
	}
	cout << res << endl;
	return 0;
}