最大异或对(trie树)

本文主要是介绍最大异或对(trie树)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

输入格式
第一行输入一个整数 N。

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

输出格式
输出一个整数表示答案。

数据范围
1≤N≤105,
0≤Ai<231
输入样例：
3
1 2 3
输出样例：
3

#include<iostream>
using namespace std;
const int N = 3000000;//一个数最多有30位二进制数*数据范围，防止越界
int a[N],n;
int idx;//节点下标
int son[N][2];
void insert(int x){
    int p = 0;
    for(int i=30;i>=0;i--){
        int u = x>>i&1;//&1可以取出右移之后的最后一位
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}
int query(int x){
    int p = 0;
    int res = 0;
    for(int i=30;i>=0;i--)
    {
        int u = x>>i&1;
        if(son[p][!u]){
            res += 1<<i;
            //res是异或后最大的答案 不是与x相异的最大数，
            //如果进入if (son[p][!s])这个语句时，
            //说明当前位置两个数不同异或完的结果是1，
            //进else的话异或完结果就是0，不需要加到答案res里。
            p = son[p][!u];
        }
        else
            p = son[p][u];
    }
    return res;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        insert(a[i]);
    }
    int res = 0;
    for(int i=0;i<n;i++)
        res = max(res, query(a[i]));
    cout<<res<<endl;
    return 0;
}

这篇关于最大异或对(trie树)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！