Xor Sum HDU - 4825

本文主要是介绍Xor Sum HDU - 4825，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=4825

01字典树模板题

贪心的考虑 肯定要先使最高位为1 在这基础上递归考虑低位 所以插入和查询时都是高位开头

 

数组版

#include <bits/stdc++.h>
using namespace std;
#define ll long longstruct node
{int c[2];int cnt;
};node tree[3000010];
ll pre[50];
int n,q,num;void init()
{int i;pre[0]=1;for(i=1;i<=31;i++) pre[i]=2ll*pre[i-1];
}void update(int val)
{int cur,i,id;cur=0;for(i=31;i>=0;i--){id=1&(val>>i);if(tree[cur].c[id]==0) tree[cur].c[id]=num++;tree[tree[cur].c[id]].cnt++;cur=tree[cur].c[id];}
}ll query(ll val)
{ll res;int cur,i,id;cur=0,res=0;for(i=31;i>=0;i--){id=1&(val>>i);if(tree[cur].c[id^1]){cur=tree[cur].c[id^1];res+=(id^1)*pre[i];}else{cur=tree[cur].c[id];res+=id*pre[i];}}return res;
}int main()
{ll val;int t,cas,i;init();scanf("%d",&t);for(cas=1;cas<=t;cas++){scanf("%d%d",&n,&q);memset(tree,0,sizeof(tree));num=1;for(i=1;i<=n;i++){scanf("%lld",&val);update(val);}printf("Case #%d:\n",cas);while(q--){scanf("%lld",&val);printf("%lld\n",query(val));}}return 0;
}

 

指针版

#include <bits/stdc++.h>
using namespace std;
#define ll long longstruct node
{node *next[2];bool cnt;
};node *root;
int n,q;void getnode(node *&ptr)
{int i;ptr=new node;for(i=0;i<2;i++) ptr->next[i]=NULL;ptr->cnt=0;
}void update(node *ptr,int *ary,int cur,int len)
{if(ptr->next[ary[cur]]==NULL) getnode(ptr->next[ary[cur]]);if(cur==len-1){ptr->next[ary[cur]]->cnt=1;return;}update(ptr->next[ary[cur]],ary,cur+1,len);
}ll query(node *ptr,int *ary,ll val,int cur,int len)
{if(cur==len) return 0;if(ptr->next[ary[cur]^1]!=NULL) return val*(ary[cur]^1)+query(ptr->next[ary[cur]^1],ary,val/2,cur+1,len);else return val*ary[cur]+query(ptr->next[ary[cur]],ary,val/2,cur+1,len);
}int main()
{ll val;int ary[50];int t,cas,i;scanf("%d",&t);for(cas=1;cas<=t;cas++){getnode(root);scanf("%d%d",&n,&q);while(n--){scanf("%lld",&val);for(i=34;i>=0;i--,val/=2) ary[i]=val%2;update(root,ary,0,35);}printf("Case #%d:\n",cas);while(q--){scanf("%lld",&val);for(i=34;i>=0;i--,val/=2) ary[i]=val%2;printf("%lld\n",query(root,ary,17179869184ll,0,35));}}return 0;
}

 

这篇关于Xor Sum HDU - 4825的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---