枚举组合,在不考虑连续的情况下判断是否可以覆盖L...R,对随机数据是一个很大的减枝.

通过检测的暴力计算一遍

ZCC loves cards

4 3 1
2 3 4 5

7

Hint
 ⊕ means xor 
 

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

int n,k,m,a[30],save[30],have[30],R,L;
bool vis[3000],cx[200];

void ckMax(int num,int sum)
{
	vis[sum]=true;
	if(num==k) return ;
	ckMax(num+1,sum^save[num]);
	ckMax(num+1,sum);
}

bool ck()
{
 	memset(vis,0,sizeof(vis));
 	ckMax(0,0);
 	for(int i=L;i<=R;i++)
 	{
 		if(vis[i]==false)	return false;
 	}
 	return true;
}

void CALU() 
{  
    if (!ck()) return;  
    for(int i=0;i<k;i++)
    	have[i]=save[i];
    do
    {
    	memset(vis,0,sizeof(vis));
    	for(int i=0;i<k;i++)
    	{
    		int x=0;
    		for(int j=0;j<k;j++)
    		{
    			x^=have[(i+j)%k];
    			vis[x]=true;	
    		}
    	}
    	for(int i=L;i<=L+k*k;i++)
    	{
    		if(vis[i]==false) break;
    		R=max(R,i);
    	}
    }while(next_permutation(have,have+k-1));
}      

void dfs(int num,int id)
{
	if(num==k)
	{
		CALU();
		return ;
	}
	for(int i=id;i<n;i++)
	{
		save[num]=a[i];
		dfs(num+1,i+1);
	}
}

int main()
{
	while(scanf("%d%d%d",&n,&k,&L)!=EOF)
	{
		R=L-1;
		for(int i=0;i<n;i++)
			scanf("%d",a+i);
		sort(a,a+n);
		dfs(0,0);
		if(R<L) printf("0\n");
		else printf("%d\n",R);
	}
	return 0;
}

HDOJ 4876 ZCC loves cards,布布扣,bubuko.com

HDOJ 4876 ZCC loves cards

原文：http://blog.csdn.net/ck_boss/article/details/38129461