AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

最大异或对为什么trie树要从高位插入二进制不是从低位?



1


题目链接 AcWing 143

为什么这个必须从最高位插入trie树?低位插入我感觉没有任何的问题啊

错误的代码:

#include <bits/stdc++.h>
using namespace std;
long long tr[1000005][3],ans,cnt;
void insert(int x)
{
    int rt=0;
    for(int i=0;i<=30;i++)
    {
        int id=(x>>i)&1;
        if(!tr[rt][id])
        tr[rt][id]=++cnt;
        rt=tr[rt][id];
    }
}
long long search(int x)
{
    long long rt=0,ans=0;
    for(int i=0;i<=30;i++)
    {
        int id=(x>>i)&1;
        if(tr[rt][!id])
        {
            ans|=(1<<i);
            rt=tr[rt][!id];
        }
        else
        rt=tr[rt][id];
    }
    return ans;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        insert(x);
        ans=max(ans,search(x));
    }
    cout<<ans;
}

把i改成n-1就对了。。。。我觉得低位都是位运算和高位是一样的啊。。。也不知道为啥wa



提问于2019-04-25 06:05
baccano
3361


1 个问答



2

因为这个题要求出异或值的最大值,所以我们要优先保证高位是1,所以在trie中要从高位插入二进制数。

举个例子:

假设有3个二进制数:

  • $(101)_2$
  • $(011)_2$
  • $(110)_2$

优先保证最高位是1,那么我们会考虑 101 ^ 011 = 110 和 011 ^ 110 = 101;
反之,如果从低位插入二进制数,那么我们实际上是优先保证低位是1,那么我们会考虑 101 ^ 110 = 011 和 011 ^ 110 = 101,得到的结果是不对的。

回答于2019-04-25 08:25
yxc
2768349

我来回答
你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息