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快結束的時候介紹的……