题目内容

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

输入格式

第一行输入一个整数N。

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

输出格式

输出一个整数表示答案。

数据范围

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

输入样例

3
1 2 3

输出样例

3

题解

代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010, M = 3000000;

int n;
int son[M][2],idx;
int a[N];

void insert(int x){
    int p = 0;
    for(int i=30;~i;i--){
        int &s = son[p][x >> i & 1];
        if (!s) s = ++idx;//创建新节点
        p = s;
    }
}

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