Solution

题目要求一对数使得异或值最大。考虑异或运算的特点：按位进行且不进位。可以想到转化为二进制数进行操作，对每一位分别处理。

把每个整数看做长度为 的 串构建字典树。最低位为字典树的叶子结点。对于数 ，在字典树中检索一次，每次都尝试沿着“与 当前位相反的字符”向下访问。若存在这样的字符指针，令答案加上当前位代表的二进制数即可。由于二进制表示下第 位比第 位到第 位之和都大，所以保证了贪心的正确性。

具体实现时，注意数组大小开 的 倍。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int ans,n,tot=1,trie[N<<5][2];
void Insert(int x){
    int y,p=1;
    for(int i=31;i>=0;i--){
        y=(x>>i)&1;
        if(!trie[p][y])
            trie[p][y]=++tot;
        p=trie[p][y];
    }
}
int query(int x){
    int y,p=1,res=0;
    for(int i=31;i>=0;i--){
        y=((x>>i)&1)^1;
        if(trie[p][y])
            res+=(1<<i),p=trie[p][y];
        else
            p=trie[p][y^1];
        if(!p)
            break;
    }
    return res;
}
int main(){
    cin>>n;
    int x;
    for(int i=1;i<=n;i++){
        cin>>x;
        ans=max(ans,query(x));
        Insert(x);
    }
    cout<<ans;
    return 0;
}