Trie字典树的巧用

字典树(Trie)是将若干个字符串建成一棵树，一条边有一个字符，从根节点出发的一条树链上的字符排起来就成了一个字符串，需要在单词的终点处打标记。

今天做了一道题，和字符串没有半毛钱关系，但是也可以使用字典树的思路来求解。

题目是这样子的

The XOR Largest Pair

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

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

第二行 N 个整数 Ai。

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

样例
Input	Output
5
2 9 5 7 0
14
数据范围与提示
对于 100% 的数据，1≤N≤10^5,0≤Ai<2^31。

这题要求所有的数中异或的最大值，如果直接暴力搜索的话，时间复杂度为O(n²)，对于本题的数据范围来说，是不可接受的。因此需要更高速的算法。

由于这里涉及到位运算，我们就可以把数字拆成二进制形式，用字典树来进行存储。这样子的话可以加速查找。由于我们需要得到异或后的值最大的数，因此我们可以使用贪心算法。只要高位尽可能的大，那么整体得到的结果就会尽可能的大。

为此，我们还需要从高位开始存储数字，以实现上述的贪心设计。

对于上面的题目，我们建立字典树，AC代码如下

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

typedef long long ll;
#define MAXN 100010

int nd[MAXN * 32][2] = {0}, cnt = 0;
bool z[MAXN * 32] = {false};

int root;
int nodes;
int tot = 0;

void Insert(int num)
{

    int nw=0;
    for (int i = 30; i >= 0; --i)
    {
        int ch = num >> i & 1;

        if (!nd[nw][ch])
            nd[nw][ch] = ++tot;
        nw = nd[nw][ch];
    }

    
}

int search(int num)
{
    int now = 0, ans = 0;
    for (int i = 30; i >= 0; --i)
    {
        
        int y = num >> i & 1;
        if (nd[now][!y]) //贪心，如果与当前位相异，则加入结果之中
        {
            ans+=1<<i;
            now = nd[now][!y];
        }
        else
        {
            now = nd[now][y];//当前位相同，继续搜索
        }
        
    }
    
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    int tmp;
    int ans=0;
    for (int i = 0; i < n; ++i)
    {
        cin >> tmp;
        Insert(tmp);
        ans = max(ans,search(tmp));//寻找与tmp异或结果最大的数，并返回异或结果

    }
    cout<<ans<<endl;
}

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~