USACO Section 2.1 Hamming Codes - 题意相当坑爹..很无聊..

就算AC了我也弄不明白输入里的B到底是要干啥~~我的程序除了输入就没用上过~~还有题意里局的那个例子更是误导人...直接举个十进制的不好非要搞奇怪的数字表示方法..题目中又根本没关系...

回到题目中..其实意思就是说要找N个10进制数..使两两之间的二进制相异位数不小于D(如0与7分别用二进制是000..111 相差的是3)..并且使得这个N个数从第一数开始比较是最小的..(如找到0 1 3比0 2 4优)..

那不就是从0开始不断递增1的找.找到一个就确定一个(因为要保证题目要求的最小)...判断可行否就是扫描所有前面确定的是不是都>=D...满足就确定这个数...

判断两个数二进制相异的位数就两个数判断对2取模是否相等..不等就不同位数+1...然后同时/=2..继续判断..直到两个数都为0了...其实这个过程和把两个数转化成两个二进制数从最低位开始比较是一个概念~~

Program:

/* ID: zzyzzy12 LANG: C++ TASK: hamming */ #include<iostream> #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<queue> using namespace std; int N,B,D,s[100],i,j,k; int check(int a,int b) { int k=0; while (a || b) { if (a%2!=b%2) k++; a/=2; b/=2; } return k; } int main() { freopen("hamming.in","r",stdin); freopen("hamming.out","w",stdout); scanf("%d%d%d",&N,&B,&D); k=0; for (i=1;i<=N;i++) while (1) { for (j=1;j<i;j++) if (check(s[j],k)<D) goto A; s[i]=k; break; A: k++; } printf("%d",s[1]); for (i=2;i<=N;i++) { if (i%10==1) printf("\n%d",s[i]); else printf(" %d",s[i]); } printf("\n"); return 0; }