XOR 游戏
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 256 Accepted Submission(s): 86
Problem Description
众所周知，度度熊喜欢XOR运算[（XOR百科）](http://baike.baidu.com/view/674171.htm)。
今天，它发明了一种XOR新游戏，最开始，它有一个长度为N的数组，度度熊可以任意添加分割线，将数组划分为M段，且每段长度小于等于L。
当然这是个和XOR有关的游戏，度度熊希望所有分组内异或和的最小值最大。
比如，长度为4的数组{1,2,3,4}，L为3，可以划分为{1|2,3,4} 或 {1,2|3,4} 或 {1,2,3|4}，最小的异或值分别为1,3,0，所以选第二种分割方法。
Input
第一行为T，表示输入数据组数。
对于每组数据，第一行包含三个整数N,M,L，第二行包含N个数，表示数组。
1≤T≤300
1≤N≤10000,1≤M≤10,1≤L≤N
1≤Ai≤109
Output
对第i组数据，输出
Case #i:
然后输出一行，仅包含一个整数，表示满足条件分组方法的最小异或值。
Sample Input
2
4 2 3
1 2 3 4
4 3 2
5 4 3 2
Sample Output
Case #1:
3
Case #2:
2
Source
2016"百度之星" - 复赛（Astar Round3）
题解：二分答案，dp[n][m]判断n个数字分成m段的可行性，那么每一段的异或和不小于mid，先处理出前缀异或和，生成ｍ棵trie树，表示保存了dp[i][j]保存的最后的前缀异或和的位置．那么转移的话，就是满足ｍax (A[j] ^ A[i] = (a[j+1] ^ a[j+2] ^ ... ^ a[i])) <= mid，求最大值就是trie里搜异或和最大，首先要求j到i的距离小于L.
#include <bits/stdc++.h>
const int N = 1e4 + 5;
struct Trie {
static const int NODE = N * 32;
int ch[NODE][2], cnt[NODE];
int sz;
void init() {
ch[0][0] = ch[0][1] = 0;
sz = 1;
}
void insert(int x) {
int u = 0;
for (int c, i=29; i>=0; --i) {
c = (x >> i) & 1;
if (!ch[u][c]) {
ch[sz][0] = ch[sz][1] = 0;
cnt[sz] = 0;
ch[u][c] = sz++;
}
u = ch[u][c];
cnt[u]++;
}
}
void _delete(int x) {
int u = 0;
for (int c, i=29; i>=0; --i) {
c = (x >> i) & 1;
int tu = u;
u = ch[u][c];
cnt[u]--;
if (!cnt[u]) {
ch[tu][c] = 0;
return ;
}
}
}
int query(int x) {
int ret = 0, u = 0;
for (int c, i=29; i>=0; --i) {
c = (x >> i) & 1;
if (ch[u][c^1]) {
ret += (1 << i);
u = ch[u][c^1];
} else {
u = ch[u][c];
}
}
return ret;
}
}trie[11];
int a[N];
bool dp[N][11];
int n, m, k;
bool check(int val) {
for (int i=0; i<=m; ++i) {
trie[i].init ();
}
for (int i=0; i<=n; ++i) {
for (int j=0; j<=m; ++j) {
dp[i][j] = false;
}
}
dp[0][0] = true;
trie[0].insert (0);
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
if (i > k && dp[i-k-1][j-1]) {
trie[j-1]._delete (a[i-k-1]);
}
if (trie[j-1].query (a[i]) >= val) {
dp[i][j] = true;
trie[j].insert (a[i]);
}
}
}
return dp[n][m];
}
int solve() {
scanf ("%d%d%d", &n, &m, &k);
for (int i=1; i<=n; ++i) {
scanf ("%d", a+i);
}
a[0] = 0;
for (int i=1; i<=n; ++i) {
a[i] = a[i-1] ^ a[i];
}
int left = 0, right = 1e9 + 7, ret = 0;
while (left <= right) {
int mid = left + right >> 1;
if (check (mid)) {
ret = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ret;
}
int main() {
int T;
scanf ("%d", &T);
for (int cas=1; cas<=T; ++cas) {
printf ("Case #%d:
%d
", cas, solve ());
}
return 0;
}