首页 > 代码库 > 【bzoj4260】Codechef REBXOR Trie树
【bzoj4260】Codechef REBXOR Trie树
题目描述
.jpg)
输入
输入数据的第一行包含一个整数N，表示数组中的元素个数。
第二行包含N个整数A1,A2,…,AN。
输出
输出一行包含给定表达式可能的最大值。
样例输入
5
1 2 3 1 2
样例输出
6
题解
Trie树
还是本着100000(2)>011111(2)的原则，显然需要从高位贪心取值。
又因为x^x=0，所以有$a_l\oplus a_{l+1}\oplus \cdots\oplus a_{r-1}\oplus a_r=(a_1\oplus a_2\oplus\cdots\oplus a_{l-2}\oplus a_{l-1})\oplus(a_1\oplus a_2\oplus\cdots\oplus a_{r-1}\oplus a_{r})$
这样如果我们知道了r，就能够贪心求出最大的异或和。
所以我们可以从左往右将前缀异或和按位加入到Trie树中，并在每次添加后贪心求出最大的异或和，记为f[i]，表示以i结尾的连续子序列的异或和的最大值。
然后再维护f[i]的前缀最大值，为1~i中所有连续子序列的异或和的最大值。
从右往左进行同样的操作，为i~n中所有连续子序列的异或和的最大值。
这样，我们枚举一个位置，它左边的最大值和它右边的最大值之和就是所求，求一下最大值即为答案。
#include <cstdio>#include <algorithm>#define N 400010using namespace std;struct data{ int next[N * 30][2] , tot; void insert(int v) { int x = 0 , i; bool t; for(i = 1 << 30 ; i ; i >>= 1) { t = v & i; if(!next[x][t]) next[x][t] = ++tot; x = next[x][t]; } } int query(int v) { int x = 0 , i , ret = 0; bool t; for(i = 1 << 30 ; i ; i >>= 1) { t = v & i; if(next[x][t ^ 1]) ret += i , x = next[x][t ^ 1]; else x = next[x][t]; } return ret; }}A , B;int a[N] , m1[N] , m2[N];int main(){ int n , i , t , ans = 0; scanf("%d" , &n); for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]); A.insert(0) , B.insert(0); for(t = 0 , i = 1 ; i <= n ; i ++ ) t ^= a[i] , A.insert(t) , m1[i] = max(m1[i - 1] , A.query(t)); for(t = 0 , i = n ; i >= 1 ; i -- ) t ^= a[i] , B.insert(t) , m2[i] = max(m2[i + 1] , B.query(t)); for(i = 1 ; i < n ; i ++ ) ans = max(ans , m1[i] + m2[i + 1]); printf("%d\n" , ans); return 0;}
【bzoj4260】Codechef REBXOR Trie树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。