HDU4825 Xor Sum(01字典树模板题）

题意:

给一个长度为n的序列，m个询问，每次询问给出一个数字x，问数组中哪个元素与x异或的值最大

思路：

1、我们按照长度为32位的二进制01字符串建树，从高位开始建。将所有数据都建到树中。

2、接下来对于每个查询，同样处理成35位二进制01字符串，对应进行查询，如果当前位子是0，那么尽量往1那边走，同理，如果当前位子是1，那么尽量往0那边走即可。

#include<iostream>
#include<algorithm>
#include<cstring>
const int maxn=1e5+10;
 using namespace std;
 typedef long long ll;
 struct Tire{
     int ch[maxn*32][2],sz;
    ll val[maxn*32];
     void init(){memset(ch,0,sizeof(ch));}
    void insert(ll x)
    {    
        int u=0;
        for(int i=32;i>=0;i--){
            int tem=(x>>i)&1;
            if(!ch[u][tem]) ch[u][tem]=++sz;
            u=ch[u][tem];
        }
        val[u]=x;
    }
    ll query(ll x)
    {
        int u=0;
        for(int i=32;i>=0;i--){
            int tem=(x>>i)&1;
            if(!ch[u][tem^1])    u=ch[u][tem];
            else u=ch[u][tem^1];
        }
        return val[u];
    }
 }Tire;
 int main()
 {
     int t,n,m,cas=0;
     ll x;
     scanf("%d",&t);
     while(++cas<=t){
         Tire.init();
         scanf("%d%d",&n,&m);
         for(int i=1;i<=n;i++) scanf("%lld",&x),Tire.insert(x);
         cout<<"Case #"<<cas<<":"<<endl;
         for(int i=1;i<=m;i++) scanf("%lld",&x),printf("%lld
",Tire.query(x));
     }
    return 0;
 }

HDU4825 Xor Sum(01字典树模板题）

相关推荐