字典树(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;
}

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

你也可能喜欢

发表评论