题目描述

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

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

第二行输入N个整数A$_1～A_N$。

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

数据范围
$1≤N\le10^5$
$0≤A_i<2^{31}$

输入样例：

3
1 2 3

输出样例：

3

注：

1.本篇题解与其它题解大体上思路一致,详情见代码注释

2.insert x 时应该循环30次,因为 $2^{31}$是1后31个0(2进制)
所以最大数据($2^31$-1)有31位,位运算的范围为 0~30
但31次好像也能过

3.因为 $n\le10^5$ 一共31位，所以数组开 tire[100100*32][3] 就够了

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int mid_in[100100];
int trie[100100*32][3];
int End[100100*32];
int top=1;

void insert(int x,int n)
{
    int pen=1;
    for(int i=30;i>=0;i--)
    {
        if(trie[pen][(x>>i)&1]==0)
            trie[pen][(x>>i)&1]=++top;
        pen=trie[pen][(x>>i)&1];
    }
    End[pen]=n; //按其它题解方法不用记录结束点(因为深度都是31)
                //但我们可以用它来记录这是第几个数
}

int find(int x)
{
    int pen=1;
    for(int i=30;i>=0;i--)
    {
        int boo=(x>>i)&1;
        if(trie[pen][!boo])
        {
            pen=trie[pen][!boo];
        }
        else
            pen=trie[pen][boo];

    }
    return mid_in[End[pen]] ^ x;    
  //通过End数组我们可以直接找出xor最大的数
}

int main()
{
    int n;
    scanf("%d",&n);
    int max_ans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&mid_in[i]);
        insert(mid_in[i],i);
        max_ans=max(max_ans,find(mid_in[i]));
    }
    cout<<max_ans<<endl;
    return 0;
}