【Codeforces 282E】Sausage Maximization 中文题意&题解&代码（C++）

E. Sausage Maximization

time limit per test2 seconds
memory limit per test256 megabytes

---

The Bitlandians are quite weird people. They have their own problems and their own solutions. They have their own thoughts and their own beliefs, they have their own values and their own merits. They have their own dishes and their own sausages!

In Bitland a sausage is an array of integers! A sausage’s deliciousness is equal to the bitwise excluding OR (the xor operation) of all integers in that sausage.

One day, when Mr. Bitkoch (the local cook) was going to close his BitRestaurant, BitHaval and BitAryo, the most famous citizens of Bitland, entered the restaurant and each ordered a sausage.

But Mr. Bitkoch had only one sausage left. So he decided to cut a prefix (several, may be zero, first array elements) of the sausage and give it to BitHaval and a postfix (several, may be zero, last array elements) of the sausage and give it to BitAryo. Note that one or both pieces of the sausage can be empty. Of course, the cut pieces mustn’t intersect (no array element can occur in both pieces).

The pleasure of BitHaval and BitAryo is equal to the bitwise XOR of their sausages’ deliciousness. An empty sausage’s deliciousness equals zero.

Find a way to cut a piece of sausage for BitHaval and BitAryo that maximizes the pleasure of these worthy citizens.

---

Input

The first line contains an integer n (1 ≤ n ≤ 105).

The next line contains n integers a1, a2, …, an (0 ≤ ai ≤ 1012) — Mr. Bitkoch’s sausage.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output

Print a single integer — the maximum pleasure BitHaval and BitAryo can get from the dinner.

Sample test(s)

input
2
1 2
output
3

input
3
1 2 3
output
3

input
2
1000 1000
output
1000

---

中文题意：
题中给出了包含 n 个数的一串数列a1, a2, …, an，规定前缀和 pre[ i ] 为前 i 个数的异或和，后缀和 suf[ i ] 为后 i 个数的异或和 （即 pre[ i ] =a1 xor a2 xor a3…….xor ai , suf[ i ]同理），现求一个前缀和 pre[ x ] 和后缀和 suf[ y ] 使得 pre [ x ] xor suf[ y ]最大,要求 x 小于 y ，即所选的前缀和后缀不能交叉
，前缀和后缀可以为空。
嘛…描述的过于繁琐了….
注意题上给的数据范围！！

---

题解：
首先我们能想到裸的n^2做法，但显然是不行的，鉴于刚刚做了一个和这类似的题且正在做字典树专题，立马想到了字典树来做……….

既然超时是因为枚举两遍，那么我们可不可以只枚举一遍呢？

想到两个数间异或的运算是两个数转成二进制后的每一位相互比较，相同为0，不同为1，既然要求最长路径，那我们就可以每次贪心的每一位都去取和自己不同数，如果找不到那就只好取相同的数，（即假如 x 的第 i 位是 0 那么他最优选择就是第 i 位为 1 的数，如果找不到第 i 位为1的就只能找第 i 位为 0 的）优先考虑最高位，再到最低位，因为二进制数 1000 是肯定大于 0XXX 的，这样的话就问题就转到了怎么在一堆序列中找到一个特定的序列，就想到了用字典树来解决问题，本题的数据比较坑，超了 int 的范围，因此要用 long long 因为最大有10^12，大概是2的四十次方左右，但因为这只是单个数的值加以来后可能会更大，所以就选择2的50次方，那么就开一个有50层的字典树，每层有0和1两个儿子，字典树从上往下存高位到低位，一遍for循环，因为不能交叉，所以当搜到第 i 个点的时候，先在字典树中插入 pre[ i-1 ]，然后再在字典树中搜匹配 nex[ i ] 的最优序列，异或后 和现有的最优答案取max，复杂度差不多是O(n*50)，就可以过这道题了。

因为数据范围是 long long ，所以有好多运算要注意转成long long 的，我也是现在才知道 （1<< x）这个运算是只能在int范围内，要在long long范围内时需写成 （1long long<< x ），被这种玩意儿坑了半小时，我也是够无奈的，知识短浅莫要见怪 ：-），orz

---

代码：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#define maxn (100005)
#define LL long long
using namespace std;
struct node{
    int ch[3];
    void init()//初始化，在这道题里没什么用，但是多组数据的话就有用了
    {
        ch[0]=0;
        ch[1]=0;
    }
}tr[maxn*50];//开字典树
int tot,n;
LL ans,pre[maxn],nex[maxn],a[maxn];//pre前缀  nex后缀
void add(LL x)//往字典树中加一个值
{
    int now=0,p=0;
    for (int i=50;i>=0;i--)
    {
        if ((1LL<<i)&x) p=1;//注意LL范围下左移的写法！！！！！！！！
        else p=0;
        if (!tr[now].ch[p])
        tot++,tr[now].ch[p]=tot,tr[tot].init();
        now=tr[now].ch[p];
    }
}
LL solve(LL x)//找到最优序列
{
    LL tmp=0;
    int now=0,p=0;
    for (int i=50;i>=0;i--)
    {
        if ((1LL<<i)&x) p=0;//!!!!!!
        else p=1;
        if (tr[now].ch[p]) tmp+=(1LL<<i);//!!!!!!!!
        else p^=1;
        now=tr[now].ch[p];
    }
    return tmp;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%I64d",&a[i]);//题中说要用I64d，=.=
        pre[i]=pre[i-1]^a[i];
    }
    for (int i=n;i>=1;i--)
    nex[i]=nex[i+1]^a[i];

    for (int i=1;i<=n+1;i++)
    {
        add(pre[i-1]);
        ans=max(ans,solve(nex[i]));//多次比较取最优
    }
    printf("%I64d\n",ans);
}