题意:给出N, b, D。找到N个数字,使得两两之间的汉明距离(Hamming distance)大于等于D,每个编码的位数为b
输出要求,每行十个数,且保证数字在b进制下值最小
解法:
枚举,从1开始(必须包含0),主要是位运算,参考nocow
/* ID: lsswxr1 PROG: hamming LANG: C++ */ #include <iostream> #include <vector> #include <map> #include <list> #include <set> #include <deque> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <cctype> #include <cstdio> #include <iomanip> #include <cmath> #include <cstdio> #include <string> #include <cstring> #include <fstream> using namespace std; #define USACO #ifdef USACO #define cin fin #define cout fout #endif ////////////////////////////////////////////////////////////////////////// ///宏定义 const int INF = 1000000000; const int MAXN = 40001; const int maxn = MAXN; ///全局变量 和 函数 int n, b, d, tot = 1; bool comp(long aa, long bb) { int cnt = 0; for (int i = 0; i < b; i++) { if ( ((aa >> i) & 1) != ((bb >> i) & 1) ) cnt++; if (cnt >= d) { return true; } } return false; } int main() { #ifdef USACO ofstream fout ("hamming.out"); ifstream fin ("hamming.in"); #endif long lists[2 << 8 - 1]; //最多8位数字 lists[0] = 0; cin >> n >> b >> d; for (long i = 1; i < ((1 << b)); i++) { if (tot > n) break; bool found = true; for (long j = 0; j < tot; j++) { if (!comp(lists[j], i)) { found = false; break; } } if (!found) continue; lists[tot++] = i; } for (int i = 0; i < n - 1; i++) { cout << lists[i] << ( ((i + 1) % 10 == 0) ? "\n" : " "); } cout << lists[n - 1] << endl; ///结束 return 0; }