此博客停更

qiancl:你认识jpy吗，比你高明到不知道哪里去了

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4260

大意：给你一列数，找出两段连续的区间[l,r],[L,R]，使得f([l,r])+f([L,R])最大，f()表示这段区间每个数按位异或。

当我看到这道题的时候，我还不知道前缀异或和的性质，然后我假设成立，写了两段代码拍了拍，发现是对的。

于是就有了一个很显然的做法，你把前缀异或和求出来一个一个数转成二进制放到一颗trie里去，对于当前1..i这些数的异或和在trie上找一串异或起来最大的串，就能知道以当前第i个点为右端点，向左能得到的最大区间异或值，同理，再求一遍后缀异或和。

然后你就得到了两个数组l,r，l[i]表示向左能取到的最大值，r[j]表示向右能取到的最大值，问题转化成求在i<j时，l[i]+r[j]的最大值，这个O(n)扫一遍就行了。

总算法复杂度O(n lgn)

代码奇丑无比（不知道怎么清空指针trie

/**************************************************************
    Problem: 4260
    User: qiancl
    Language: C++
    Result: Accepted
    Time:5020 ms
    Memory:196220 kb
****************************************************************/
 
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 400010
struct node{node *ch[2];}root,root1,tree[30*N],tree1[30*N];
int n,m,p,k,mx,ans,p3,o[N],l[N],r[N],L[N],R[N];bool f[31];
inline void add(bool a[]){
    node *loc=&root;int k=1;
    while(k<=30){
        if(loc->ch[a[k]]==NULL)loc->ch[a[k]]=&tree[p++];
        loc=loc->ch[a[k]],++k;
    }
}
inline void add1(bool a[]){
    node *loc=&root1;int k=1;
    while(k<=30){
        if(loc->ch[a[k]]==NULL)loc->ch[a[k]]=&tree1[p3++];
        loc=loc->ch[a[k]],++k;
    }
}
#define nc() getchar()
inline int read(){
    int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
    for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
inline int find(bool a[]){
    node *loc=&root;int k=1,o=1<<29,ans=0;
    while(k<=30){
        if(loc->ch[a[k]^1]==NULL)ans+=o*(a[k]),loc=loc->ch[a[k]];
        else ans+=o*(a[k]^1),loc=loc->ch[a[k]^1];++k,o>>=1;
    }return ans;
}
inline int find1(bool a[]){
    node *loc=&root1;int k=1,o=1<<29,ans=0;
    while(k<=30){
        if(loc->ch[a[k]^1]==NULL)ans+=o*(a[k]),loc=loc->ch[a[k]];
        else ans+=o*(a[k]^1),loc=loc->ch[a[k]^1];++k,o>>=1;
    }return ans;
}
int main(){
    n=read(),add(f),add1(f);
    for(int i=1;i<=n;o[i]=read(),++i);
    for(int i=1,x=0,k;i<=n;++i){
        x=(L[i]=o[i]^L[i-1]),k=30,memset(f,0,sizeof f);
        while(x)f[k--]=x%2,x>>=1;
        add(f),l[i]=L[i]^find(f);
    }
    for(int i=n,x=0,k;i>=1;--i){
        x=(R[i]=o[i]^R[i+1]),k=30,memset(f,0,sizeof f);
        while(x)f[k--]=x%2,x>>=1;
        add1(f),r[i]=R[i]^find1(f);
    }ans=0;int mx=0;
    for(int i=1;i<n;++i){
        if(l[i]>mx)mx=l[i];
        if(mx+r[i+1]>ans)ans=mx+r[i+1];
    }
    printf("%d",ans);
}

loading...