【USACO 2.1】Hamming Codes

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


下一篇:svn: Can't convert string from 'UTF-8' to native encoding 的解决办法(转)