9
25
2015
4

4260: Codechef REBXOR

4260: Codechef REBXOR

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 89  Solved: 36
[Submit][Status][Discuss]

Description

 

Input

输入数据的第一行包含一个整数N,表示数组中的元素个数。
第二行包含N个整数A1,A2,…,AN。
 
 

 

Output

输出一行包含给定表达式可能的最大值。
 

 

Sample Input

5
1 2 3 1 2

Sample Output

6

HINT

 

满足条件的(l1,r1,l2,r2)有:(1,2,3,3),(1,2,4,5),(3,3,4,5)。

对于100%的数据,2 ≤ N ≤ 4*105,0 ≤ Ai ≤ 109。

 

 

Source

    Orz 豆豆神犇。。。全机房第一个做这道题的。。然后教会了全机房——>

                             http://qiancl.is-programmer.com/

    作者道题之前需要先知道一个规律。。。xor的逆运算也是xor。。所以我们可以通过前缀得出任意一段的xor值。。。对于求一个位置pos为结尾的xor值最大的一段,可以在它前面的前缀xor中从二进制高位向低位找是否可以使这个位置为1。。。然后后缀也做一遍。。。最后就可以O(n)扫一遍得出答案了

    至于维护之前的xor值我们可以用一个字母树维护。。每次在树上找出xor最大。。记录后把当前这个店的前缀xor插入树中

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 4e5;
int a[N],b[N],c[N],L[N],R[N],f[40],ans,n,next[15100000][2],len,cnt,Max;
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
void Work(int x){
	memset(f,0,sizeof(f));len = 0;
	while (x){f[++len] = x&1;x>>=1;}
}
int Query(){
	int res = 0,now = 0;
	for (int i=32;i;i--){
		if (next[now][f[i]==0]) {res+=(1<<(i-1));now = next[now][f[i]==0];}
		else now = next[now][f[i]];
	}
	return res;
}
void Insert(){
	int now = 0;
	for (int i=32;i;i--){
		if (!next[now][f[i]]){++cnt;next[now][f[i]] = cnt;now = cnt;}
		else now = next[now][f[i]];
	}
}
int main(){
	n = read();
	for (int i=1;i<=n;i++) a[i] = read();
	for (int i=1;i<=n;i++) b[i] = a[i]^b[i-1];
	for (int i=n;i;i--) c[i] = a[i]^c[i+1];
	Work(0);Insert();
	for (int i=1;i<=n;i++){
		Work(b[i]);
		L[i] = max(b[i],Query());
		Insert();
	}
	memset(next,0,sizeof(next));cnt = 0;
	Work(0);Insert();
	for (int i=n;i;i--){
		Work(c[i]);
		R[i] = max(c[i],Query());
		Insert();
	}
	for (int i=1;i<=n;i++){
		Max = max(Max,L[i]);
		ans = max(Max+R[i],ans);
	}
	printf("%d",ans);
}
Category: BZOJ题解 | Tags: | Read Count: 492
Avatar_small
meepo 说:
2015年9月25日 21:04

@qiancl: 跪烂神犇。。求加友链。。。


登录 *


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