4260: Codechef REBXOR
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 89 Solved: 36
[Submit][Status][Discuss]
Description
.jpg "在新窗口打开")
Input
输入数据的第一行包含一个整数N，表示数组中的元素个数。
第二行包含N个整数A1,A2,…,AN。
Output
输出一行包含给定表达式可能的最大值。
Sample Input
5
1 2 3 1 2
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插入树中
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #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);} |
2015年9月25日 20:18
%%%就是强
2015年9月25日 21:04
@qiancl: 跪烂神犇。。求加友链。。。
2015年9月28日 19:55
@meepo: 已加
2015年9月28日 19:56
@qiancl: %%%%