题目描述

在给定的$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
输出样例：
3

异或性质+前缀+字典树

这道题目很难想到是字典树,如果不是放在字典树单元的话.

其实来说,一个整数,是可以转化成为一个32位的二进制数,而也就可以变成长度为32位的二进制字符串.

既然如此话,那么我们可以这么做,每一次检索的时候,我们都走与当前$A_i$这一位相反的位置走,也就是让Xor值最大,如果说没有路可以走的话,那么就走相同的路.

因为这样就可以遍历所有的情况呀，对于每一个数字选择的都是前面和它异或产生的值最大的数字，即使当前数字是和后面的某个数字异或值最大，遍历后面那个数字的时候就会将这个数字选择出来
by @pfco

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define fic(i,a,b) for(int i=a;i>=b;i--)
#define fir(i,a,b) for(int i=a;i<=b;i++)
const int N=100100;
int trie[N*32][2],tot=1,a[N],n,ans;
void insert(int x) 
{
    int p=1;
    fic(k,30,0)
    {
        int ch=x>>k&1;
        if (trie[p][ch]==0) 
            trie[p][ch]=(++tot);
        p=trie[p][ch];
    }
}
int Search(int x)
{
    int p=1,ans=0;
    fic(k,30,0)
    {
        int ch=x>>k&1;//取出第k位
        if (trie[p][ch^1])//异或走路
        {
            p=trie[p][ch^1];
            ans|=(1<<k);
        }
        else
            p=trie[p][ch];
    }
    return ans;
}
int main()
{
    cin>>n;
    fir(i,1,n)
    {
        scanf("%d",&a[i]);
        insert(a[i]);
        ans=max(ans,Search(a[i]));//取最大值
    }
    cout<<ans<<endl;
}