hdu5715XOR sum

/*
这道题目要求将n长度的序列分为m段，每段长度小于等于L，使得这些段的异或和的最小值最大
最小值最大，二分x，n分为m段每段异或和都大于等于x
dp[i][k]=max(min(dp[j][k-1],A[i]^A[j]),dp[i][k]) {j属于 {1..i-1} AND (i-j<k)}
}
然后用01字典树优化，保证去01字典树里找到和A[i]异或的最大的那一个 
A[j]要在01字典树里的话保证dp[j][k-1]是能够得到的状态
*/
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1e4+10;
struct Trie                         //建立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 (c) printf("c[%d]=%d\n",i,c);
			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 del(int x)   //删除trie树 
	{
		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)  //查询trie树 
	 {
	 	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++)    //建立m颗trie树 
	  trie[i].init();
	for  (int i=0;i<=n;i++)
	 for  (int j=0;j<=m;j++)     //即划分为m段 
	   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]) //段的最前面间隔 ,因为满足若i-k-1成立，则必定[i-k..i]成立01在一维中背包单调递增 
	   	    trie[j-1].del(a[i-k-1]);
		if (trie[j-1].query(a[i])>=val){    //找到和a[i]异或最大的那个前缀异或，并且异或和大于等于x即可 
			dp[i][j]=true;
			trie[j].insert(a[i]);//s[j]要在01字典树里的话要保证dp[j][k-1]是能够得到的状态 
		} 
	  }
    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];    //维护异或前缀和，一个好的性质是A[i]^A[j]=a[i]^a[i+1]^....^a[j-1]^a[j] 
	 int left=0,right=1e9+7,ret=0;    //二分最小值 ，是否满足异或和最大 
	 while (left<=right)
	 {
	 	int mid=(left+right)/2;
	 	if (check(mid)){
	 		ret=mid;
	 		left=mid+1;
		 }
		 else {
		 	right=mid-1;
		 }
	  } 
    return ret;
} 


int main()
{
  int _;
  scanf("%d",&_);
  for (int cas=1;cas<=_;cas++)
  { printf("Case #%d:\n%d\n",cas,solve());
  }
  return 0;
}