Trie树的经典题目

题目

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

输入输出

输入：第一行输入一个整数 N。
第二行输入 N 个整数 A1～AN。
输出：输出一个整数表示答案。

思路

暴力做法

for(int i = 0; i < n; i ++){    //枚举第一个数
    for (int j = 0; j < n; j ++ ){  //枚举第二个数
        res = max(res, a[i] ^ a[j]);
    }
}

用trie优化内层循环，在ai到ai-1中找到aj与ai的异或最大。
数据范围是每个整数最多31位，把每个数看成长度为31的二进制。
tire树的两个分支是所有第i位是0的数、所有第i位是1的树。每次尽量往和当前位不同的分支走，最后得到异或的结果最大。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 31 * N;   //M是结点数
int son[M][2];  //trie树
int idx;

void insert(int x){     //在trie树中插入x
    int p = 0;
    for(int i = 30; i >= 0; i --){
        int u = x >> i & 1;
        if(!son[p][u])  son[p][u] = ++idx;
        p = son[p][u];
    }
}

int search(int x){  //在trie树中查询与x异或最大的数
    int p = 0;
    int res = 0;
    for(int i = 30; i >= 0; i --){
        int u = x >> i & 1;
        if(son[p][!u]){     //先找与当前位不同的分支
            res = res * 2 + !u;
            p = son[p][!u];
        }
        else{
            res = res * 2 + u;
            p = son[p][u];
        }
    }
    return res;
}

int main()
{
    int n;
    int res = 0;
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        int x;
        cin >> x;
        insert(x);
        int t = search(x);
        res = max(res, x ^ t);
    }
    cout << res;
    return 0;
}