题目链接 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

提问于1 month, 3 weeks ago

baccano

321