牛客练习赛42-SHTMYCBDFTT

链接：https://ac.nowcoder.com/acm/contest/393/B
来源：牛客网

注意本题有模数

给定一个 长度为 n 的序列 { a } ，求：

max1≤i≤j≤n{(ai⊕ai+1⊕⋯⊕aj)+(ai+ai+1+⋯+aj)}mod100000007max1≤i≤j≤n{(ai⊕ai+1⊕⋯⊕aj)+(ai+ai+1+⋯+aj)}mod100000007

其中 ⊕⊕ 表示异或

输入描述:

第一行一个整数 n 。
第二行 n 个整数，表示 aiai 。

输出描述:

一行一个整数 ans ，表示答案。

示例1

输入

复制

3
1 2 3

输出

复制

6

说明

我们 显然需要将所有的数字都选上显然需要将所有的数字都选上，此时 ans=(1⊕2⊕3)+1+2+3=6ans=(1⊕2⊕3)+1+2+3=6 。

备注:

对于所有的数据，保证 1≤n≤3×105,0≤ai<2201≤n≤3×105,0≤ai<220 。

样例：想不到吧，你的做法至少能过样例！

 

这题笑死我算了，点进去之后是这样的。。

 

这个模数...可是一顿好找...

 

令xor(i)表示前i项的异或值，如果xor(l,r)表示第l项到第r项的异或值，那么xor(l,r)=xor(r)⊕xor(l−1)。

（证明:假设一个长度为4的数组,x=x1^x2^x3^x4，若求x3^x4,那么x3^x4=x^(x1^x2) =x1^x1^x2^x2^x3^x4，x1^x1=0, x2^x2=0，任何数与0异或为本身，所以xor(l,r)=xor(r)⊕xor(l−1)）

建立一个前缀和数组，一个前缀异或数组。

区间异或最大值一定出现在(i,n) 1<=i<n这个区间里，所以循环n-1次，找出区间异或+区间和的最大值即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
const int MAXN(3*1e5);
const int INF(0x3f3f3f3f);
const int mod(100000007);
typedef long long int LL;
LL a[MAXN+50];
LL sum[MAXN+50];
LL xo[MAXN+50];
int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        xo[i]=xo[i-1]^a[i];
    }
    LL ans=0;
    for(int i=0;i<n;i++) {
        ans=max(ans,(sum[n]-sum[i])+(xo[n]^xo[i]));
    }
    cout<<ans%mod<<endl;
}