首页 > 代码库 > Codeforces 282E. Sausage Maximization【trie树（非指针版）】

Codeforces 282E. Sausage Maximization【trie树（非指针版）】

2024-07-21 16:49:46   223人阅读

题目大意：

给出一串数，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树（非指针版）】


联系
我们