USACO 2.1.5 Hamming Codes

题意:给出N, b, D。找到N个数字,使得两两之间的汉明距离(Hamming distance)大于等于D,每个编码的位数为b

输出要求,每行十个数,且保证数字在b进制下值最小

 

解法:

枚举,从1开始(必须包含0),主要是位运算,参考nocow

USACO 2.1.5 Hamming Codes
/*
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;
}
USACO 2.1.5 Hamming Codes

USACO 2.1.5 Hamming Codes

上一篇:Paxos可容错的一致性协议


下一篇:Java判断字符串是中文还是英文