首页 > 代码库 > 【HDU】5269 ZYB loves Xor I
【HDU】5269 ZYB loves Xor I
【算法】trie
【题解】
为了让数据有序,求lowbit无法直接排序,从而考虑倒过来排序,然后数据就会呈现出明显的规律:
法一:将数字倒着贴在字典树上,则容易发现两数的lowbit就是它们岔道结点的深度,所以先建树后对于一个数字依次把每次分岔开的另一边的size乘上权值累加答案。
法二:从高位到低位分组求和,即第一位1在上,0在下,则两边之间互相计算过后就再无影响,只剩下各自内部的事情再处理。由于排序后数据的有序性使分治可行。
法三:排序后对于一个数字,它和后面的数字的lowbit有单调性……然后可以维护它,相当麻烦,不再赘述。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=50010,MOD=998244353; int size[maxn*50],t[maxn*50][2],tot,a[maxn],n; void insert(int x,int dep,int num) { if(dep>30)return; if(t[x][num&1]) { size[t[x][num&1]]++; } else { t[x][num&1]=++tot; t[t[x][num&1]][0]=t[t[x][num&1]][1]=0; size[t[x][num&1]]=1; } insert(t[x][num&1],dep+1,num>>1); } int query(int x,int dep,int num) { if(dep>30)return 0; long long ansnow=((t[x][(num&1)^1]?size[t[x][(num&1)^1]]:0)<<dep)%MOD; if(t[x][(num&1)])ansnow=((ansnow+query(t[x][num&1],dep+1,num>>1)))%MOD; return (int)(ansnow%MOD); } int main() { int T,now=0; scanf("%d",&T); long long ans=0; while(T--) { now++; tot=1; t[1][0]=t[1][1]=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); insert(1,0,a[i]); } ans=0; for(int i=1;i<=n;i++)ans=(ans+query(1,0,a[i]))%MOD; printf("Case #%d: %d\n",now,(int)(ans%MOD)); } return 0; }
【HDU】5269 ZYB loves Xor I
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。