首页 > 代码库 > Codeforces 282E. Sausage Maximization【trie树(非指针版)】
Codeforces 282E. Sausage Maximization【trie树(非指针版)】
题目大意:
给出一串数,pre[i](前i个数的异或)为a[0]~a[i-1]的异或,post[i](后缀的异或)为a[i]~a[n-1]的异或,求pre[i]^post[j]的最大值(0<=i<=j<=n),其中,pre[0]=0,post[n]=0(表示一个数都不选)。
做法:
利用trie树将后缀或者前缀存储起来,首先从pre[n]开始,往前遍历,对于每个前缀,将此时的后缀添加到trie树中,再在trie中寻找与当前前缀异或之后能得到最大的值。
在trie中存储数的时候,将该数的二进制的数位的每一位存进去,由于异或之后不可能增加位数,那么我们要找最大的值的话,只需要从第一位开始,保证这一位能为1的时候取一,如果不能取一则取0,那么最后的结果一定是最大的。
这里用的trie树是非指针版的。。自己写的,觉得指针太复杂(自己太弱....),用存储节点下标的方式。
注意存储数的时候,需要将40位全部存进去(2^40是大于10^12的第一个二次幂数),不然处理位数会很麻烦。这样的话,trie树中节点数最多也就40*10^5个,也是可行的。
由于数的范围是10^12,会爆int,得用long long ,还得特别小心特别小心!像(1<<40)这样的操作是会爆int的,必须写成这样(1LL<<40)才行。博主在这里被坑了好久。。要不是大牛提醒的话,我都不知道什么时候才能发现这个问题。。。推掉重写也是有可能的!。。。
详细见代码和注释:
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #define N 100010 using namespace std; struct node { long long nxt[2];//存储nxt节点在数组中的下标 }trie[N*40]; long long all_idx,bit[42],num[N],n; long long createNode() { memset(trie[all_idx].nxt,-1,sizeof(trie[all_idx].nxt));//没有访问过的置为-1 return all_idx++; } void insert_Node(long long root,long long cur) { memset(bit,0,sizeof(bit));//存储cur的二进制数 long long len=0; while(cur) { bit[len++]=cur&1; cur>>=1; } long long idx=root; //将40位全部存进去 for(len=40;len>=0;len--) { long long k=bit[len]; if(trie[idx].nxt[k]==-1) trie[idx].nxt[k]=createNode(); idx=trie[idx].nxt[k]; } } long long running(long long root,long long cur) { long long sum=0; memset(bit,0,sizeof(bit)); long long len=0; while(cur) { bit[len++]=cur&1; cur>>=1; } long long idx=root; for(len=40;len>=0;len--) { long long k=!bit[len];/////两个数不相同,异或结果为1 if(trie[idx].nxt[k]!=-1) { sum+=(1LL<<len);///////一定要加LL,被坑了好久。。。也是无语了 idx=trie[idx].nxt[k]; } else idx=trie[idx].nxt[!k];//如果不存在这样的数,只能取0,并且从这边走下去。 } return sum; } int main() { scanf("%I64d",&n); long long pre=0,post=0; long long ans=0; for(long long i=0;i<n;i++) scanf("%I64d",num+i),pre^=num[i]; long long root=createNode(); for(long long i=n-1;i>=0;pre^=num[i],post^=num[i],i--) { insert_Node(root,post); ans=max(ans,running(root,pre)); } ans=max(ans,running(root,pre));//判断取0个前缀的时候的值 cout<<ans<<endl; return 0; }
Codeforces 282E. Sausage Maximization【trie树(非指针版)】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。