算法1

C++ 代码

#include <cstdio>
#include <algorithm>
using namespace std;

int son[100010*31][2],a[100010],idx;
int b[31],k,sum;

int twototen(int a[])//将二进制数组算出其十进制结果
{
    int sum = 0;
    for(int i = 29,k = 2; i >= 0; i --)
    {
        sum += k*a[i];
        k = 2*k;
    }
    return sum + a[30];
}

void maxxor(int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        int p = 0;
        for (int j = 30; j >= 0; j--)//将二进制存入trie树中
        {
            int u = (a[i] >> j) & 1;
            if (!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
        }
    }

    for (int i = 0; i < n; i++)//查询每一个数字的最大异或对
    {
        int p = 0;
        k = 0;
        for (int j = 30; j >= 0; j--)
        {
            int u = (a[i] >> j) & 1;
            if (u == 0 && son[p][1])//存在不相同的分支就往不相同的那边走
            {
                b[k] = 1;
                k ++;
                p = son[p][1];
            }
            else if (u == 1 && son[p][0])
            {
                b[k] = 1;
                k++;
                p = son[p][0];
            }
            else
            {
                k++;
                p = son[p][u];
            }
        }
        sum = max(sum,twototen(b));//计算当前最大的异或值的十进制
        for (int i = 0; i < 31; i++)//进行下一个数字的最大异或值查询
            b[i] = 0;
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; i++) scanf("%d",&a[i]);
    maxxor(a, n);
    printf("%d",sum);
    return 0;
}