trie 143. 最大异或对

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

输入格式

第一行输入一个整数 NN。

第二行输入 NN 个整数 A1A1～ANAN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤1051≤N≤105,
0≤Ai<2310≤Ai<231

输入样例：

3
1 2 3

输出样例：

3

代码

#include
#include
 
using namespace std;
 
const int N=100010,M=31*N;
int n;
int a[N],son[M][2],idx;
 
void insert(int x)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int &s=son[p][x>>i&1];
        if(!s)  s=++idx;
        p=s;
    }
}
 
int search(int x)
{
    int p=0,res=0;
    for(int i=30;i>=0;i--)
    {
        int s=x>>i&1;
        if(son[p][!s])
        {
            res+=1<
            p=son[p][!s];
        }
        else    p=son[p][s];
    }
    return res;
}
 
int main()
{
    scanf("%d",&n);
    for(int i=0;i
    {
        scanf("%d",&a[i]);
        insert(a[i]);
    }
    
    int res=0;
    for(int i=0;i
    {
        res=max(res,search(a[i]));
    }
    
    printf("%d\n",res);
    return 0;
}

今天下午暗下决心做三个题目，结果发现做这一个题目就已经非常吃力了。这个题目其实暑假的时候就已经看了题解，早几天看了讲解视频，还是有一些一知半解的。

主要的思路是建立一个trie树，然后异或运算是不进位加法，意思就是说，一个数字用二进制方法来表示，如果对应数位上的数字不相同，结果就是1，如果两个数字相同，结果就是0。

我们先把输入的数字使用二进制来进行表示，二进制表示使用算术右移和&运算来进行实现。

x>>i&1

我们知道，数位越高，对数字的影响越大，所以我们从最高位开始考虑问题。

insert函数是用来建立一个trie树的

search函数是用来寻找当前数字的最大的异或数值

假设我们现在数位是1，我们需要的数字就是0，我们选择有0的数字去进行异或运算，如果没有0，我们再去考虑其他情况，有点像是有很多数字可以供选择，我们选择一个满足条件的最优解

res+=1<

这一行是进制的知识，就是把分散的数字归整成为一个十进制数字，可能会成为最后的答案数值