最大异或对

题目

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

输入格式

第一行输入一个整数N。

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

输出格式

输出一个整数表示答案。

数据范围

1≤N≤105,
0≤Ai<231

输入样例:

3
1 2 3

输出样例:

3

分析:

  • trie树模板题,先将所有数看成二进制串加入trie树,然后查询所有数在trie数中每个二进制位尽量往相反位置走的结果。每次更新结果即可。

代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+5,M=3e6,English=2;

int trie[M][2],a[N],idx;
int n,m;

//将k插入trie树 
void trie_insert(int k){
    int p=0;
    for(int i=30;~i;i--){
        int t=k>>i&1;
        int &x=trie[p][t];
        if(!x) x=++idx;
        p=x;
    }
}

//查询与在tire树中每位与K尽量相反的路 
int trie_search(int k){
    int p=0;
    int ans=0;
    for(int i=30;~i;i--){
        int x=k>>i&1;
        if(trie[p][!x]){
            ans+=1<<i;
            p=trie[p][!x];
        }else if(trie[p][x]) {
            p=trie[p][x];
        }else break;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){//将所有值插入trie 
        cin>>a[i];
        trie_insert(a[i]);
    }
    int ans=0;
    for(int i=0;i<n;i++){//查询每个值在trie树中最大的异或值 
        int temp=trie_search(a[i]);
        ans=max(temp,ans);
    }
    cout<<ans<<endl;
    return 0;
}

   转载规则


《最大异或对》 蒋曾辉 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录