当前位置: 首页 > 工具软件 > Sausage > 使用案例 >

Codeforces Round #173 (Div. 2) E - Sausage Maximization (01字典树)

平嘉熙
2023-12-01

题意:

给你n个数字,找出一个前缀一个后缀,使得前缀和后缀所有的数异或后最大,前后缀都可以为空但不能有重合部分

思路:

当我处理某个后缀的时候,它符合题意的前缀是已知的,如果我们预处理出前缀和后缀,那么后缀的值我们是知道的,而因为我们要进行的是异或操作,那么从二进制的角度来看,我们是可以贪心地找出这个后缀和哪个前缀异或后值最大。(比如我们假设某个数的二进制是从右到左的,那么我们从左到右去贪心,遇到1那么我们优先找0,反之亦然,然后不断更新值,这样贪心的结果就是异或后最大的)
那么我们就可以,一个个地把前缀放入字典树,然后用后缀去贪心。因为我们的前缀是一个个放入字典树,我们某个后缀符合题意得前缀就不会有疏漏,这样不断更新字典树和ans,就能得到我们的答案了。

错误及反思:

一开始是枚举后缀去删前缀。。。。相当麻烦,所以cnt数组写搓了,各种wa,有时候觉得难度太大就应该重新审视下思路的。。。

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int tire[maxn*50][2],root,tot,n;
long long arr[maxn],ans=0,pre[maxn],rev[maxn];
int newnode()
{
    memset(tire[tot],-1,sizeof(tire[tot]));
    return tot++;
}
void add(long long x)
{
    int now=root;
    for(int i=50;i>=0;i--)
    {
        long long k=x>>i&1;
        int ne=0;
        if(k) ne=1;
        if(tire[now][ne]==-1)
            tire[now][ne]=newnode();
        now=tire[now][ne];
    }
}
long long Find(long long x)
{
    int now=root;
    long long temp=x;
    for(int i=50;i>=0;i--)
    {
        long long k=(x>>i)&1;
        int ne=0;
        if(k) ne=1;
        if(ne)
        {
            if(tire[now][0]!=-1)
            {
                now=tire[now][0];
            }
            else
            {
                temp-=1ll<<i;
                now=tire[now][1];
            }
        }
        else
        {
            if(tire[now][1]!=-1)
            {
                temp+=(1ll<<i);
                now=tire[now][1];
            }
            else
            {
                now=tire[now][0];
            }
        }
    }
    //printf("%I64d\n",temp);
    return temp;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%I64d",&arr[i]);
    for(int i=1;i<=n;i++)
        pre[i]=pre[i-1]^arr[i];
    for(int i=n;i>=1;i--)
        rev[i]=rev[i+1]^arr[i];

    tot = 0;
    root = newnode();

    for(int i=0;i<=n;i++)
    {
        add(pre[i]);
        ans=max(ans,Find(rev[i+1]));
    }
    printf("%I64d\n",ans);
}
 类似资料: