首页 > 代码库 > 【USACO 2.1】Hamming Codes

【USACO 2.1】Hamming Codes

/*TASK: hammingLANG: C++URL:http://train.usaco.org/usacoprob2?a=5FomsUyB0cP&S=hammingSOLVE: 找粗一个值最小的n个元素的集合,每个元素都是不超过m位二进制的数,且两两之间二进制位不同的位不小于d。dfs,枚举每一个数,枚举范围:(前一个数,1<<m),每次进入dfs都判断一下当前集合是否满足两两距离不小于d。 */#include<cstdio>int n,m,d;int a[1024];int dis(int a,int b){	int d=0;	for(int i=0;i<m;i++)		if((a&(1<<i))^(b&(1<<i)))			d++;	return d;}bool ck(int n){	for(int i=0;i<n-1;i++)		for(int j=i+1;j<n;j++)			if(dis(a[i],a[j])<d)return 0;	return 1;}bool dfs(int x){	if(!ck(x))return 0;	if(x==n){		for(int i=0;i<n;){			printf("%d",a[i++]);			for(int j=2;j<=10&&i<n;j++,i++)				printf(" %d",a[i]);			puts("");		}		return 1;	}	for(int i=x?a[x-1]+1:0;i<1<<m;i++){		a[x]=i;		if(dfs(x+1))return 1;	}	return 0;}int main(){	freopen("hamming.in","r",stdin);	freopen("hamming.out","w",stdout);	scanf("%d%d%d",&n,&m,&d);	dfs(0);}

  

【USACO 2.1】Hamming Codes