9
22
2015
0

【Water】bzoj4260Codechef REBXOR

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...

Category: bzoj | Tags: | Read Count: 470

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com