E. [USACO2.1] 海明码 Hamming Codes

Type: RemoteJudge

1000ms

125MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给出 $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 距离至少为 $\bm d$ ，因此也可以大于 $\bm d$ 。

USACO 2.1

翻译来自NOCOW