acwing 143. 最大异或对

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

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

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

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

数据范围
1≤N≤105,
0≤Ai<231
输入样例：
3
1 2 3
输出样例：
3

暴力试试——超时TLE

#include
#include
using namespace std;
const int N = 100010;
int a[N];

int main()
{
    int res = 0;
    int n;
    scanf("%d", &n);
    
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    for(int i = 0; i < n; i++)
    {
        for(int j = i+1; j < n; j++)
        {
            res = max(res, a[i]^a[j]);
        }
    }
    printf("%d", res);
    
    return 0;
}

使用trie树

#include
#include
#include

using namespace std;

const int N = 3000010; // 每个数有31位，然后一共最多1e5个数
int a[N];
int son[N][2], idx;

void insert(int x)
{
    int p = 0;
    for(int i = 30; i >= 0; i--)
    {
        int t = (x >> i) & 1; // 取x的第i位， i从30到0共31位
        if(!son[p][t]) son[p][t] = ++idx;
        p = son[p][t];
    }
    
}

// 返回与x异或后最大的结果
int query(int x)
{
    int p = 0;
    int res = 0;
    for(int i = 30; i >= 0; i--)
    {
        int t = (x >> i) & 1;
        if(son[p][!t])  // 和x第i位不同的节点有没有，如果有的话异或后该位就是1
        {
            res += 1 << i;
            p = son[p][!t];
        }
         //p = son[p][!t];
        else
        {
            // res += 0 << i;
            p = son[p][t];
        }
    }
    return res;
}

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