143.最大异或对

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

输入格式

第一行输入一个整数 NN。

第二行输入 NN 个整数 A1A1～ANAN。

输出格式

输出一个整数表示答案。

数据范围

1 ≤N ≤ 10^{5
0 ≤A.i < 2}31

输入样例：

3
1 2 3

输出样例：

3

题解：

#include<iostream>
using namespace std;

const int N = 1e5+10, M = 3100010; //M代表一个数字串二进制可以到多长
int a[N], son[M][2], idx, n;

void insert(int x){
    int p = 0;//根节点
    for (int i = 30 ; ~i ; i --){
        int &s = son[p][x >> i & 1]; //取x的第i位的二进制数是什么
        if (!s) s = ++ idx;//如果插入中发现没有该子节点，就开出这条路
        p = s;//指针指向下一层
    }
}
int search(int x){
    int p = 0 , res = 0;
    for (int i = 30 ; ~i ; i --){ //从最大位开始找
        int s = x >> i & 1;
        if (son[p][!s]){ // 如果当前层有对应相同的数
            res += 1 << i;//左移1位，相当于乘2
            p = son[p][!s]; //p指针就指向不同的数
        }else p = son[p][s];
    }
    return res;
}

int main(){

    int n;
    cin >> n;
    for (int i = 0 ; i < n ; i ++)
    {
        scanf("%d",&a[i]);
        insert(a[i]);
    }

    int res = 0;
    //search(a[i])查找的是a[i]的值得最大与或值
    for (int i = 0 ; i < n ; i ++) res = max(res, search(a[i]));

    printf("%d", res);

    return 0;
}

这道题的启示是：字典树不单单可以高效存储和查找字符串集合,还可以存储二进制数字
思路:将每个数以二进制方式存入字典树,找的时候从最高位去找有无该位的异.