[Acwing143] 最大异或对

• Trie树

在给定的 \(N\) 个整数 \(A_1，A_2……A_N\)中选出两个进行 \(xor\)（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 \(N\)。

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

输出格式

输出一个整数表示答案。

数据范围

\(1≤N≤10^5\),
\(0≤Ai<2^{31}\)

题解

如果要找到与某个数最大异或的数，最理想的情况是2进制开始每位数字都是相反的。于是我们可以用Trie树将这些数的二进制串储存起来，定义search 操作在树上跑，对于每个节点，假设当前要找的串停在了1，如果节点 0 存在，那么进入0，异或结果就左移一位加上1，如果不存在那么进入节点1，异或结果只左移。

由于\(0 \leq A_i<2^{31}\)，Trie深度最多只有\(D = 30\)，因此搜索操作时间复杂度是 \(O(D)\) 的常数级别，我们要线性扫描，对每个数找出最大异或值，因此总的时间复杂度是 \(O(Dn)\)。整棵树最多有\(Dn\) 个节点，因此空间复杂度为 \(O(Dn)\)

• 时间复杂度 \(O(Dn)\)
• 空间复杂度 \(O(Dn)\)

题解代码

#include
using namespace std;
const int N = 100010,M = 3000300;
int a[N],son[M][2],idx=0;

void insert(int x){
    int p = 0;
    for(int i = 30;i>=0;i--){
        int u = x>>i & 1;
        if(!son[p][u])son[p][u] = ++idx;
        p = son[p][u];
    }
}

//
int search(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+1;
        }
        else{
            p = son[p][u];
            res = res*2;
        }
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin>>n;

    for(int i=0;i>a[i];
        insert(a[i]);
    }
    
    int res = 0;
    for(int i = 0;i