题目描述

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

输入格式
第一行输入一个整数N。

第二行输入N个整数A1～AN。

输出格式
输出一个整数表示答案。

数据范围
1≤N≤105,
0≤Ai<231

样例

3
1 2 3

算法1

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <cmath>


using namespace std;


const int N=100010,M=31*N;
int n;
int a[N];
int son[M][2],idx;//字典树存储字符串或者二进制数，idx记录下标

int main()
{
    cin>>n;
    int res = 0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];

    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            res = max(res,a[i]^a[j]);
        }
    }
    cout<<res<<endl;

    return 0;
}

算法2

(字典树存储优化)

时间复杂度

参考文献

C++ 代码

//进行优化

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 query(int x)
{
    int p=0,res=0;
    for(int i=30;i>=0;i--)//i>=0,等价于~i(对i取反)
    {
        int s = x>>i&1;
        if(son[p][!s])
        {
            res += 1<<i;//1向左移位，移位累加
            p = son[p][!s];
        }
        else p = son[p][s];
    }

    return res;
}

int main()
{
    cin>>n;
    int res = 0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        insert(a[i]);

    }
    for(int i=0;i<n;i++)
    {
        res = max(res,query(a[i]));
    }

    cout<<res<<endl;

    return 0;
}