usaco-2.1.5 海明码

题目描述

给定 $N, B, D$ ，在 $B$ 位编码的取值范围 $[0, 2^B-1]$ 中选出 $N$ 个互不相同的数，使得任意两个的海明距离（二进制不同位的个数）都不小于 $D$ 。输出按升序排列，每行 10 个；若有多解，输出化为 $2^B$ 进制后数值最小的那一组。

数据范围： $1 \le N \le 64$ ， $1 \le B \le 8$ ， $1 \le D \le 7$ 。

样例输入：16 7 3

样例输出：

text

1
20 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127

思路

最优解首项必为 $0$ ：把任意合法解整体异或 $a_1$ 后仍合法且首项更小。于是逐位贪心：已选最后一个编码 $+1$ 开始往后扫，第一个与已选所有编码海明距离均 $\ge D$ 的数就接上去。高位优先保证了贪心正确。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 03:38
# update_at: 2026-10-01 03:38

import sys

PER_LINE = 10  # 题面要求每行输出 10 个编码


def hamming_code(n: int, b: int, d: int) -> list[int]:
    """贪心构造字典序最小的 n 个 b 位编码：每步只接上最小的合法编码。"""
    space = 1 << b  # b 位编码的取值空间 [0, 2^b)
    code = [0]      # 0 一定在某个最优解里：把任意解整体异或上它自己的最小元即可
    for _ in range(n - 1):
        # 只在比当前最大编码更大的一侧扫描，输出天然递增；all(...) 就是两两海明距离校验
        nxt = next(
            (x for x in range(code[-1] + 1, space)
             if all((x ^ y).bit_count() >= d for y in code)),
            None,
        )
        if nxt is None:  # 空间容纳不下 n 个编码，能选几个算几个
            break
        code.append(nxt)
    return code


def solve() -> None:
    n, b, d = map(int, sys.stdin.buffer.read().split())
    code = hamming_code(n, b, d)
    lines = [' '.join(map(str, code[i:i + PER_LINE])) for i in range(0, len(code), PER_LINE)]
    print('\n'.join(lines))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 09:46
 * update_at: 2026-10-06 09:46
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 70;

int n, b, d;
int code[MAXN];      // 已选编码
int cnt;             // 已选个数

// 计算 x 与 y 的海明距离（不同二进制位的个数）
int hamming_dist(int x, int y) {
    int t = x ^ y;
    int res = 0;
    while (t) {
        res += t & 1;
        t >>= 1;
    }
    return res;
}

// 判断 x 与已选所有编码的海明距离是否都 >= d
bool valid(int x) {
    for (int i = 0; i < cnt; ++i) {
        if (hamming_dist(x, code[i]) < d)
            return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> b >> d)) return 0;

    int space = 1 << b;   // 编码取值范围 [0, 2^b)
    code[0] = 0;          // 最优解首项必为 0
    cnt = 1;

    for (int i = 1; i < n; ++i) {
        int nxt = -1;
        for (int x = code[cnt - 1] + 1; x < space; ++x) {
            if (valid(x)) {
                nxt = x;
                break;
            }
        }
        if (nxt == -1) break; // 空间不够，能选几个算几个
        code[cnt++] = nxt;
    }

    for (int i = 0; i < cnt; ++i) {
        if (i > 0 && i % 10 != 0) cout << ' ';
        cout << code[i];
        if ((i + 1) % 10 == 0) cout << '\n';
    }
    if (cnt % 10 != 0) cout << '\n';

    return 0;
}

目录

题目描述

思路

参考代码