XOR 游戏

题目连接：

Description

众所周知，度度熊喜欢XOR运算。

今天，它发明了一种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

Hint

题意

题解：

两种方法，一种是按位分析，一种是二分答案

二分答案的话，我们令dp[i][j]表示考虑到第i个数，我划分了j次，是否最小值的答案超过了mid

这个就直接dp转移就好了，每次我们在字典树里面找到最大的a[i]^a[k]，然后从dp[k][j-1]转移过来就好了

转移的前提是dp[k][j-1]也是合法的

代码

#include
    
     using namespace std;const int maxn = 5e5+5;int a[maxn],n,m,k,cnt[12];struct node{    int ch[2],sum;    void init()    {        ch[0]=ch[1]=sum=0;    }}T[12][maxn];void add(int p,int x){    int cur = 1;    T[p][cur].sum++;    for(int i=30;i>=0;i--)    {        int y = x>>i&1;        if(!T[p][cur].ch[y])T[p][cur].ch[y]=++cnt[p];        cur=T[p][cur].ch[y];        T[p][cur].sum++;    }}void del(int p,int x){    int cur = 1;    T[p][cur].sum--;    for(int i=30;i>=0;i--)    {        int y = x>>i&1;        if(!T[p][cur].ch[y])T[p][cur].ch[y]=++cnt[p];        cur=T[p][cur].ch[y];        T[p][cur].sum--;    }}int query(int p,int x){    int cur=1,ans=0;    if(T[p][1].sum==0)return 0;    for(int i=30;i>=0;i--)    {        int y = x>>i & 1;        if(T[p][T[p][cur].ch[y^1]].sum)            ans+=1<
     
      k&&dp[i-k-1][j])                del(j,a[i-k-1]);            int tmp=query(j,a[i]);            if(tmp>=mid)            {                add(j+1,a[i]);                dp[i][j+1]=1;            }        }    }    return dp[n][m];}void solve(int cas){    scanf("%d%d%d",&n,&m,&k);    for(int i=1;i<=n;i++)scanf("%d",&a[i]);    for(int i=1;i<=n;i++)a[i]^=a[i-1];    int l=0,r=1e9+7,ans=l;    while(l<=r)    {        int mid=(l+r)/2;        if(check(mid))l=mid+1,ans=mid;        else r=mid-1;    }    printf("Case #%d:\n%d\n",cas,ans);}int main(){    int t;    scanf("%d",&t);    for(int i=1;i<=t;i++)        solve(i);    return 0;}