首页 > 其他 > 详细

HDU 4825 Xor sum

时间:2017-12-09 11:36:28      阅读:221      评论:0      收藏:0      [点我收藏+]

trie树的异或和问题

本题是一道经典题,使用trie树维护所给出的集合,我们知道等比数列前n项的和比第n+1项小,所以本题可以使用贪心策略,对于每一个询问,我们从高位向低位匹配,寻找最大异或值,向下递归求解。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define LL unsigned long long
using namespace std;
const int MAXN=3200000+5;
LL init(){
    LL rv=0,fh=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') fh=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        rv=(rv<<1)+(rv<<3)+c-'0';
        c=getchar();
    }
    return fh*rv;
}
struct node{
    int nxt[2];
}trie[MAXN];
LL T,n,num,nume,m;
void ins(const LL id){
    LL u=0;
    for(int i=31;i>=0;i--){
        bool v=(id>>i)&(LL)1;
        if(!trie[u].nxt[v]) trie[u].nxt[v]=++nume;
        u=trie[u].nxt[v];
    }
}
LL query(const LL id){
    LL u=0,ans=0;
    for(int i=31;i>=0;i--){
        bool v=(id>>i)&(LL)1;
        if(trie[u].nxt[!v]){
            ans=(ans<<1)+!v;
            u=trie[u].nxt[!v];
        }else{
            ans=(ans<<1)+v;
            u=trie[u].nxt[v];
        }
    }
    return ans;
}
int main(){
    freopen("in.txt","r",stdin);
    T=init();
    while(T--){
        printf("Case #%d:\n",++num);
        n=init();m=init();
        for(int i=1;i<=n;i++){
            int t=init();
            ins(t);
        }
        for(int i=1;i<=m;i++){
            int t=init();
            printf("%d\n",query(t));
        }
        memset(trie,0,sizeof(trie));
        nume=0;
    }
    fclose(stdin);
    return 0;
}

HDU 4825 Xor sum

原文:http://www.cnblogs.com/Mr-WolframsMgcBox/p/8010846.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!