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 
     
      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:\n%d\n", cas, solve ());    }    return 0;}