题解：P5657 [CSP-S2019] 格雷码
mc_xiexie
·
·
题解
前言
格雷码是一个二进制数系，其中两个相邻数的二进制位只有一位不同。举个例子，3 位二进制数的格雷码序列为。
注意序列由 $0$ 开始。
格雷码由贝尔实验室的 Frank Gray 于 1940 年提出，并于 1953 年获得专利。
### 构造方法
#### 手动构造
1. 翻转最低位得到下一个格雷码；（将 $1$ 变为 $0$，将 $0$ 变为 $1$）
2. 把最右边的 $1$ 的左边的位翻转得到下一个格雷码。
经 $2^{k-1}$ 次就可得到 $k$ 位的格雷码序列。
#### 镜像构造
$k$ 位的格雷码可以从 $k-1$ 位的格雷码以上下镜射后加上新位的方式快速得到。
例如 $3$ 位格雷码。
###### 注：红色字体为原有，蓝色为镜像，绿色为加的新位。
通过观察我们发现加的新位原有加 $1$，镜像加 $0$。这很好理解，原有的已经确定，新的更大要加。
证明我就不证了，感兴趣可以看 [oi-wiki](https://oi-wiki.org//misc/gray-code/#正确性证明)。
参考文献：[格雷码 - OI Wiki](https://oi-wiki.org//misc/gray-code/)。