（板子）AcWing 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 <bits/stdc++.h>
using namespace std;
long long int b[35];
int son[3000010][3];
int idx=0;
long long int ans=0;
int n;
void Insert(int x)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        //printf("%d %d\n",x>>i&1,son[p][x>>i&1]);
        if(son[p][x>>i&1]==0)
            son[p][x>>i&1]=++idx;
        p=son[p][x>>i&1];
    }

}
void ques(int x)
{
    long long int sum=0;
    int p=0;
    for(int i=30;i>=0;i--)
    {
        if(x>>i&1==1)
        {
            if(son[p][0]!=0)
            {
                sum+=b[i];
                p=son[p][0];
            }
            else
            {
                p=son[p][1];
            }
        }
        else
        {
            if(son[p][1]!=0)
            {
                sum+=b[i];
                p=son[p][1];
            }
            else
                p=son[p][0];
        }

    }
    ans=max(ans,sum);

}
int main()
{
    memset(son,0,sizeof(son));
    long long int a[100010];
    b[0]=1;
    /*for(int i=31;i>=0;i--)
    {
        printf("%d",2>>i&1);
    }
    printf("\n");*/
    for(int i=1;i<=30;i++)
    {
        b[i]=b[i-1]*2;
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        Insert(a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        ques(a[i]);
    }
    printf("%lld\n",ans);
    return 0;
}