[C++知识库]143.最大异或对 【字典树】【Trie】

143. 最大异或对

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

输入格式

第一行输入一个整数 N。

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

输出格式

输出一个整数表示答案。

数据范围

1≤N≤10^5,
0≤Ai<2^31

输入样例：

3
1 2 3

输出样例：

3

这道题如果没有标签的提示的话，很难想到可以用字典树来完成，不过Ai的数据范围提到了2^31,也不难想到字典树还可以存储二进制数字。

思路:将每个数以二进制方式存入字典树,找的时候从最高位去找有无该位的异.

c++代码

#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include <unordered_map>
using namespace std;
const int N=100010;
int a[N],son[N*31][2],idx;
void insert(int x){
    int p = 0; // 
    for (int i = 31; i >= 0; i--)
    {
        int u = x >> i & 1; 
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}
int find(int x){
    int p=0,ans=0;
    for (int i = 31; i >= 0; i--)
    {
        int u = x >> i & 1;
        if (!son[p][u^1])
        {
            p = son[p][u];
            ans *=2 ; 
        }else
        {
            p = son[p][1^u];
            ans=ans*2+1;
        }
    }
    return ans;
}
int main(){
    int n,ans=0;
    cin>>n;

    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        insert(a[i]);
        ans=max(ans,find(a[i]));
    }
    cout<<ans;
    return 0;
}