hamming解题报告
------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
找出N个二进制数，每个数有B位，使得各数两两之间“海明距离”至少为D。（若有多组解，输出字典序最小的。）
海明距离是指：两个二进制数不同二进制位的个数。
【数据范围】
1<=N<=64
1<=B<=8
1<=D<=7
【输入格式】
一行三个数N、B、D，空格分割。
【输出格式】
从小到大输出，每行输出十个数。
【输入样例】
16 7 3
【输出样例】
0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
又是一道枚举，贪心即可。
最多256个数，从0开始扫（从小到大），能取的就取了，并且把所有与之距离小于D的数“删掉”。这样一来，取的就只可能是最优解了。由于本题不可能无解（题目都没说无解咋办，当然有解。。），而且删数的时间也就是256，因此总时间比62500稍大，常熟大约是8，完全可以接受。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】
第二次AC。
第一次提交没过，忘了USACO要求的输出末尾换行。。
------------------------------------------------------------------------------------------------------------------------------------------------
【代码】
/*
ID: icedrea1
PROB: hamming
LANG: C++
*/ #include <iostream>
#include <fstream>
using namespace std; void DtoB(int num)
{
int bit[],l=;
while(num) { bit[l++]=num&; num>>=; }
for(int i=l;i<;++i) cout<<;
for(int i=l-;i>=;--i) cout<<bit[i];
}
void look()
{
ifstream in("hamming.out"); int num;
while(in>>num)
{
DtoB(num);
cout<<endl;
} in.close();
} // just a look -----------------------------------------------------------
// go~! int N,B,D;
bool have[]; int num[],sum; int dis(int x,int y)
{
int s=;
while(x||y) { s+=(x^y)&; x>>=; y>>=; }
return s;
} void del(int x)
{
for(int y=;y<(<<B);++y)
if(dis(x,y)<D) have[y]=false;
} void print(ostream &out)
{
for(int i=;i<sum-;++i) out<<num[i]<<(i%==?"\n":" ");
out<<num[sum-]<<endl;
} int main()
{
//look(); return 0;
ifstream in("hamming.in");
ofstream out("hamming.out"); in>>N>>B>>D;
for(int x=;x<(<<B);++x) have[x]=true;
for(int x=;x<(<<B) && sum<N;++x)
{
if(!have[x]) continue;
num[sum++]=x; del(x);
} if(sum<N) out<<"not enough!"<<endl; else print(out); in.close();
out.close();
return ;
}