题目名称 682. 海明码
输入输出 hamming.in/out
难度等级 ★
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 祝一帆 于2012-03-30加入修改该题
开放分组 全部用户
提交状态
分类标签
USACO 搜索法 位运算
分享题解
通过:100, 提交:131, 通过率:76.34%
1020 100 0.000 s 0.00 MiB C++
李冠辰 100 0.000 s 0.00 MiB C++
李昊泽 100 0.000 s 0.00 MiB C++
王国正 100 0.000 s 0.00 MiB C++
郝子煦 100 0.000 s 0.00 MiB C++
徐家齐 100 0.000 s 0.00 MiB C++
超人 100 0.000 s 0.00 MiB C++
刘一澈 100 0.000 s 0.00 MiB C++
张子衿 100 0.002 s 0.17 MiB Pascal
侯静茹 100 0.002 s 0.17 MiB Pascal
本题关联比赛
20140713下午练习
二进制状态表示之搜索中的应用
位运算及及其应用题单
关于 海明码 的近10条评论(全部评论)

682. 海明码

★   输入文件:hamming.in   输出文件:hamming.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

给出 $n,b,d$,要求找出 $n$ 个由 $0,1$ 组成的编码,每个编码有 $b$ 位,使得两两编码之间至少有 $d$ 个单位的 **Hamming 距离**。


**Hamming 距离**是指两个二进制编码中的不同二进制位的数目。例如,编码 `0101 0101 0100` 和 `0010 0011 0100` 之间的 **Hamming 距离**是 $5$:

0101 0101 0100
0010 0011 0100
 ^^^  ^^

【输入格式】

一行三个整数 $n,b,d$。

【输出格式】

输出字典序最小的解($n$ 个编码同样也要升序输出),每输出 $10$ 个编码换一行。

你需要先将每个编码当成二进制数,再将其转成十进制数输出。

【样例输入】

16 7 3

【样例输出】

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

【数据规模与约定】

对于 $100\%$ 的数据,$1\le n \le 64$,$1\le b \le 8$,$1\le d \le 7$。

**请注意:题目中只要求 Hamming 距离至少为 $d$,因此也可以大于 $d$。**

【来源】

USACO 2.1