在给定的N个整数A1，A2……ANA1，A2……AN中选出两个进行xor（异或）运算，得到的结果最大是多少？
第一行输入一个整数N。
第二行输入N个整数A1A1～ANAN。
输出一个整数表示答案。
1≤N≤1051≤N≤105,
0≤Ai<2310≤Ai<231
3
1 2 3
3
算法：01字典树 + 位运算 + 异或性质
题解：首先我们并看不出来这个题目需要用到字典树，但是，我们可以发现数据的范围只有31位，那么我们就可以同过这个点来建立关于位数的字典树。首先，我们把每个数的二进制看作一个字符串，然后开始建树...查询的话，就是每次匹配异或1之后的数（假如是1，你就找0，相反，则找1），如果每次找到的是异或之后的数，你就把当前位赋1。
#include <iostream> #include <cstdio> using namespace std; const int maxn = 1e5+7; int tree[maxn * 30][2]; int tot; void insert(int x) { int root = 0; for(int i = 30; i >= 0; i--) { int idx = (x >> i) & 1; //获取每位的值 if(tree[root][idx] == 0) { tree[root][idx] = ++tot; } root = tree[root][idx]; } } int search(int x) { int ans = 0; int root = 0; for(int i = 30; i >= 0; i--) { int idx = (x >> i) & 1; if(tree[root][1 ^ idx] != 0) { ans |= (1 << i); //如果当前位不同，就把当前位赋1 root = tree[root][1 ^ idx]; } else { root = tree[root][idx]; } } return ans; } int main() { int n; scanf("%d", &n); int ans = 0; for(int i = 1; i <= n; i++) { int x; scanf("%d", &x); insert(x); ans = max(ans, search(x)); } printf("%d\n", ans); return 0; }
AcWing：143. 最大异或对（01字典树 + 位运算 + 异或性质）
原文：https://www.cnblogs.com/buhuiflydepig/p/11306057.html