[CSP-S 2019] 格雷码

GitHub跳转原题关系图返回列表

利用二进制反射格雷码公式 k xor (k >> 1)，直接求出编号 k 对应的 n 位编码。

OJ: luogu

题目 ID: P5657

难度:普及/提高-

标签:位运算构造

日期: 2026-05-31 16:38

目录

  1. 题意
  2. 思路
    1. 关键公式
    2. 小表格理解
    3. 实现细节
  3. 代码
  4. 复杂度
  5. 总结

题意

题目给出一种递归生成格雷码的规则。

1 位格雷码是：

text
0
1

如果已经知道 n 位格雷码，那么 n+1 位格雷码这样生成：

  1. 前一半：把 n 位格雷码按原顺序排列，并在前面补 0；
  2. 后一半：把 n 位格雷码按逆序排列，并在前面补 1。

例如 2 位格雷码是：

text
00 01 11 10

现在给出 n 和编号 k，要求输出这个递归规则下第 k 个 n 位格雷码。

注意编号从 0 开始，且答案必须输出成恰好 n 位，不足的高位要补 0。

思路

最直接的想法是按照题目的递归定义去找第 k 个串。

先看一个可以直接验证想法的朴素解：

cpp
// brute.cpp：小数据/教学版，按格雷码的递归定义直接定位第 k 个串。
#include <bits/stdc++.h>
using namespace std;

int n;
unsigned long long k;

// solve_gray(len, idx)：返回 len 位格雷码中编号为 idx 的二进制串。
string solve_gray(int len, unsigned long long idx) {
    if (len == 1) {
        return idx == 0 ? "0" : "1";
    }

    unsigned long long half = 1ULL << (len - 1);

    if (idx < half) {
        // 前半段：保持 len-1 位格雷码原顺序，前面补 0。
        return "0" + solve_gray(len - 1, idx);
    }

    // 后半段：使用 len-1 位格雷码的逆序，前面补 1。
    unsigned long long reversed_idx = (half - 1) - (idx - half);
    return "1" + solve_gray(len - 1, reversed_idx);
}

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

    cin >> n >> k;
    cout << solve_gray(n, k) << '\n';

    return 0;
}

这个暴力没有生成全部 2^n 个串，而是递归定位第 k 个串：

  • 如果 k 落在前半段，答案第一位是 0，剩下部分继续找原顺序里的第 k 个；
  • 如果 k 落在后半段，答案第一位是 1，剩下部分要找逆序里的对应位置。

它非常贴近题意，适合理解“前半顺序、后半逆序”的构造。但正式写法可以更短。

关键公式

题目中的递归构造就是标准的二进制反射格雷码。编号为 k 的格雷码可以直接计算：

gray=k⊕(k>>1) gray = k \oplus (k >> 1)

其中 ^ 或 ⊕\oplus 表示按位异或。

为什么这个公式成立？

把普通二进制编号 k 写成：

text
k      = b[n-1] b[n-2] ... b[1] b[0]
k >> 1 = 0      b[n-1] ... b[2] b[1]

两者异或后，得到的每一位表示“相邻两位是否不同”：

text
gray[i] = b[i+1] xor b[i]

格雷码的本质正是记录这种变化。普通二进制编号每次加一时，低位可能连续翻转；但这些连续翻转经过相邻异或后会互相抵消，只留下一个变化位置，所以相邻格雷码只差一位。

小表格理解

这张表展示 n = 3 时，普通编号如何通过公式变成格雷码：

k 二进制 k k >> 1 k ^ (k >> 1) 格雷码
0 000 000 000 000
1 001 000 001 001
2 010 001 011 011
3 011 001 010 010
4 100 010 110 110
5 101 010 111 111
6 110 011 101 101
7 111 011 100 100

这正好和题面中 3 位格雷码的顺序一致。

实现细节

n 最大是 64，k 最大可能接近 264−12^{64}-1，所以用 unsigned long long 保存 k。

计算完：

cpp
gray = k ^ (k >> 1)

之后，从第 n-1 位到第 0 位输出即可。

不要写 1ULL << n 来判断范围，因为当 n = 64 时，左移 64 位是不合法的。我们的输出循环最多只会移动到第 63 位，因此是安全的。

代码

cpp
// main.cpp：用公式 gray = k ^ (k >> 1) 求第 k 个 n 位格雷码。
#include <bits/stdc++.h>
using namespace std;

int n;
unsigned long long k;

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

    cin >> n >> k;

    unsigned long long gray = k ^ (k >> 1);

    for (int bit = n - 1; bit >= 0; bit--) {
        cout << ((gray >> bit) & 1ULL);
    }
    cout << '\n';

    return 0;
}

复杂度

  • 时间复杂度：O(n)O(n)，只需要输出 n 位。
  • 空间复杂度：O(1)O(1)。

总结

这题的关键是认出题目给出的递归构造就是二进制反射格雷码。

递归定义能帮助理解顺序：前半补 0，后半逆序补 1。但真正实现时，只需要记住公式：

gray=k⊕(k>>1) gray = k \oplus (k >> 1)

最后按 n 位输出即可。边界上最需要注意的是 n = 64，不要计算 2^n，只输出已有整数的各个二进制位。

本文的 main.cpp 已用递归定义版 brute.cpp 进行 300 组随机对拍，覆盖了 1 <= n <= 64 的随机合法编号。