CF1847C Vampiric Powers, anyone? 题解

· · 题解

分析

我们在数列 a 需要选出一个区间，使得这个区间中的数异或起来的值尽可能大。

异或很多个数我们是不好处理的，所以我们考虑求出数列 a 的前缀异或数组 x。

接下来我们的问题就转化成了，在 0 \sim n 中选择两个整数 i,j，使得 x_i \oplus x_j 的值尽可能大，要注意 0 也是可以选的。

首先思考 O(n^2) 的暴力做法。两重循环，第一重枚举 i，第二重枚举 j，统计最大值。

发现 a_i 的值域很小，导致了 x_i 的值域也很小，那我们考虑开个桶，将 x 放到桶里。

现在，暴力做法的第二重循环可以枚举 0 \sim V，其中 V 为 x_i 的上限 2^8-1。此时时间复杂度为 O(V \cdot \sum n)，可以通过。

注意不能两重循环都枚举 0 \sim V，因为这样时间复杂度会和 t 挂钩，O(tV^2) 是无法接受的。

代码

const int N=1e5+5,P=256;
int n,a[N],x[N],q[1<<9],ans,temp;
void solve(){
    n=read(),ans=0;
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) x[i]=x[i-1]^a[i];
    for(int i=0;i<=n;i++) q[x[i]]=temp;
    for(int i=0;i<=n;i++) for(int p=0;p<P;p++) if(q[p]==temp) ans=max(ans,x[i]^p);
    cout<<ans<<endl;
}
signed main(){
    int T;
//  cin>>T;
    T=read();
    for(temp=1;temp<=T;temp++) solve();
    return 0;
}