USACO 2.1 Hamming Codes

        看到这道题的第一印象，是联想到八皇后。第一个想到的是回溯法，然而题意只要求最优解，所以实现上采用了DFS的搜索方式，找到解就返回。

        细节上，判断两个数字“距离”是否大于指定值，我的做法是，先对两个数字做位的异或——这里用到了官方之前对位运算的说明，再计算这个数字的二进制有几个1。

        迭代时，每次函数遍历可选的数字，从中找到与前方选定的每个数字距离都远的数字，在前方选定的数字序列基础上增加这个数字，如果已经符合了要求的长度，那么就返回这组数字，如果没有，那么就进行下一轮的迭代。

        附上代码：

#include <iostream>
#include <fstream>
using namespace std;

const int MAXN = 64;
int N, B, D;
int b;
int* resSer;

bool isFar(int n1, int n2)
{
    int r = n1 ^ n2;
    int cnt;
    for (cnt = 0; r; r &= r - 1)
        cnt ++;
    return cnt >= D;
}

bool findSer(int* clct, int clctLen, int s)
{
    int i, j;
    bool flag;

    for (i = s; i < b; i ++) {
        for (j = 0; j < clctLen; j ++) {
            if (!isFar(i, clct[j])) {
                flag = true;
                break;
            }
        }
        if (flag) {
            flag = false;
            continue;
        }

        clct[clctLen] = i;
        if (clctLen + 1 == N) {
            resSer = clct;
            return true;
        }
        if (findSer(clct, clctLen + 1, i))
            return true;
    }
    return false;
}

int main()
{
    ifstream fin ("hamming.in");
    ofstream fout ("hamming.out");
    int i, n;

    fin >> N >> B >> D;
    for (i = 0, b = 1; i < B; i ++, b *= 2);

    int* clct = new int[MAXN];
    findSer(clct, 0, 0);

    for (i = 0, n = 0; i < N; i ++) {
        fout << resSer[i];
        if (n < 9 && i != N - 1)
            fout << " ";
        n ++;
        if (n == 10) {
            n = 0;
            fout << endl;
        }
    }
    if (n != 0)
        fout << endl;
}
           

        闲话时间。这又是一道逻辑很清楚的问题，一开始做题的时候，我反而担心因为迭代和比较次数过多，导致超时。实际用时却少得惊人，只能理解成位运算的用时比我想象得要小得多吧。

        另外要吐槽的地方是，USACO的文章编排有点飘忽，这一章用到了位运算，但是位运算是在Chapter 1快结束的时候介绍的……