[C++][算法基础]最大异或对(Trie树)

在给定的 N 个整数 $A_{1}$ ， $A_{2}$ ...... $A_{N}$ 中选出两个进行 xor（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 N。

第二行输入 N 个整数 $A_{1}$ ~ $A_{N}$ 。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤ $10^{5}$ ,
0≤ $A_{i}$ < $2^{31}$

输入样例：

3
1 2 3

输出样例：

代码：

#include<iostream>
using namespace std;

const int N = 100010, M = 3000000;

int son[M][2],num[N],idx;

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

int query(int x){
    int p = 0,res = 0;
    for (int i = 30;i>=0;i--){
        int s = x >> i & 1;
        if(son[p][!s] != 0){
            res += (1 << i);
            p = son[p][!s];
        }else{
            p = son[p][s];
        }
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    for(int i = 0;i<n;i++){
        cin>>num[i];
        insert(num[i]);
    }
    int res = 0;
    for(int i = 0;i<n;i++){
        res = max(res,query(num[i]));
    }
    cout<<res<<endl;
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/525868.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！