首页 > 代码库 > 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树(非指针版)】