USACO Training Section 2.1 Hamming Codes

英文原题 中文题译

大致题意：
    给定N、B、D，找N个二进制位数不大于B（即<2^B）的数使得其两两间二进制海明距离至少为D，要求输出最小的序列，每十个数一行。

样例输入N=16,B=7,D=3
输出的二进制分析：
0000000 : 0    1110000 : 7   1001100 : 25   0111100 : 30
0101010 : 42   1011010 : 45  1100110 : 51   0010110 : 52
1101001 : 75   0011001 : 76  0100101 : 82   1010101 : 85
1000011 : 97   0110011 : 102 0001111 : 120  1111111 : 127
可以看到这些数其实是很有规律的，应该可以推算出来（相当于在B维网格上找N个距离为D的点）。比如：
规律1：距离为3，则前3位从0到7循环变化，每两个数为一组，刚好在前3位取反；
规律2：4－5位从0开始，从0到3循环变化，每4个数为一组，组内两两取反。
...这样，7＝3＋2＋1＋1，可以推算出全部数值。不过要编程实现，需要全部细节，这就不继续考虑了。

实现采取暴力方式，从0开始逐个搜，比较每个数与前面已存的数的海明距离，满足条件则保存。从B<=8也就知状态空间足够小，方案可行。且：B这个参数事实上无用，题目给的数据会使得满足条件的数的位数不大于B，否则无解。题意中无无解这项，也就是可以不考虑B。

计算海明距离采用之前N皇后问题同样的方法：先求两数的异或，使相同位都为0，不同位为1.然后得到最低位的1，不断的减去，从而计算二进制表示中1的个数，即其海明距离。

需要注意的是输出的格式，USACO严格要求格式：第一个数前不能有空格，每行最后一个数后不能有空格，整个输出必须以\n结束。

/*
ID: blackco3
TASK: hamming
LANG: C++
*/
#include <fstream>
using namespace std;
#define _max_ 64
int _num, _len, _dis, _nums[_max_]={0} ;

inline int hamming_dis( int n1, int n2 ){
	register int dif= n1^n2, count=0, pos ;
	while( dif )
		pos = dif & -dif , dif -= pos , count++;
	return count ;
}

inline int test_dis(int cnum, int npre) {
	for( int i=0; i<npre; i++ )
		if( hamming_dis(cnum, _nums[i])<_dis )
			return 0 ;
	return 1 ;
}

int main() {	
	ifstream fin("hamming.in");
	ofstream fout("hamming.out");	
	fin >> _num >> _len >> _dis ;
	for( int i=0, cur=0 ; i<_num; i++ ){
		while( !test_dis(cur,i) )		
			cur++;
		_nums[i]=cur++ ; 
		if( i%10 )
			fout << " " ;
		fout << _nums[i] ;
		if( !((i+1)%10) || i==_num-1)
			fout << endl ;
	}
	return 0;
}