[CSP-S 2019] 格雷码

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

从按定义递归定位、生成整张表，到沿编号逐步翻转，最后化简成公式 k xor (k >> 1)，逐层拿满 50、80、95、100 分。

OJ: luogu

题目 ID: P5657

难度:普及-

标签:位运算构造递推

创建: 2026-05-31 16:38

更新: 2026-10-07 10:45

形式化题目

给定 $n$ 和编号 $k$ （ $0 \leqslant k < 2^n$ ），按下面的规则给所有 $n$ 位二进制串排一个序，输出排在第 $k$ 个的串：

$1$ 位格雷码是 0，1；
$n$ 位格雷码的前 $2^{n-1}$ 个串，是把 $n-1$ 位格雷码按原顺序排列后统一补前缀 0；
后 $2^{n-1}$ 个串，是把 $n-1$ 位格雷码按逆序排列后统一补前缀 1。

编号从 $0$ 开始，输出必须是恰好 $n$ 位、允许前导零的二进制串。

解法路线

题面给出了四个真实的分数档位。它们的区别不在 $n$ 本身，而在允许你浪费多少存储和多少时间：

档位	真实约束	最省事的做法	瓶颈
$50\%$	$n \leqslant 10$	按定义逐层生成整张格雷码表	表里有 $2^n$ 个串
$80\%$	$k \leqslant 5 \times 10^6$	从 $0$ 号串沿编号一步一步推到 $k$	$k$ 次迭代
$95\%$	$k \leqslant 2^{63}-1$	套用反射格雷码公式 $k \oplus (k \gg 1)$	$k$ 超出有符号 `long long` 上界
$100\%$	$1 \leqslant n \leqslant 64$	同上，改用无符号 $64$ 位整数	无

这些档位不是「复杂度从坏到好」的单调序列，而是「约束越松，能用的实现越笨」。四份分档代码都能独立提交、各自拿到对应分数，正式主解是最后一档的 main.cpp。

在按档位写实现之前，先给出一个最直译定义的递归解法。它不参与分档，作用是当作后面公式法的对照与对拍基准。

暴力解法：按定义递归定位

适用范围

这是最贴近题面文字的写法：不生成整张表，只顺着定义一路定位到第 $k$ 个串。它不按分数档位设计，任意 $n$ 都能跑，放在这里是为了给后面的公式法提供一个独立于公式的正确性基准。

称它为「暴力」是指「逐字翻译定义、不做任何化简」，不是指复杂度差：因为题面定义本身就是线性递归，所以这份基准的时间也是 $O(n)$ 。代价是后半段的逆序下标和 $2^{63}$ 的边界很容易写错，这正是后面公式法要绕开的东西。

思路

要求 $len$ 位格雷码里编号为 $idx$ 的串，就看 $idx$ 落在哪一半：

前半段（ $idx < 2^{len-1}$ ）：这一位填 0，剩下的部分仍然去 $len-1$ 位格雷码里按原顺序找编号 $idx$ ；
后半段：这一位填 1，剩下的部分要去 $len-1$ 位格雷码的逆序里找。原顺序的第 $idx$ 个，在逆序里对应编号

(2^{len-1} - 1) - (idx - 2^{len-1})

一路递归到 $len = 1$ 为止。

代码

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/**
 * 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 20:28
 * update_at: 2026-10-01 20:28
 */
// brute.cpp：小数据/教学版，按格雷码的递归定义直接定位第 k 个串，用来辅助对拍。
// 每一层只做一次选择：判断 k 落在前半段还是后半段，再决定这一位填 0 还是 1。
// 递归深度只有 n 层，所以 n = 64 也能跑；它只是写法朴素，不代表复杂度高。
#include <bits/stdc++.h>
using namespace std;

// 与 main.cpp 保持一致的输入范围：k 可能达到 2^64-1，必须用无符号 64 位。
typedef unsigned long long ull;

int n; // 编码位数
ull k; // 编号

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

    ull half = 1ULL << (len - 1); // 前半段的串数，len <= 64 时最多到 2^63

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

    // 后半段：使用 len-1 位格雷码的逆序，前面补 1。
    ull 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;
}

复杂度与瓶颈

每层只递归一次，时间 $O(n)$ ，空间 $O(n)$ （递归深度）。复杂度本身没问题，麻烦全在实现细节：后半段的逆序编号必须推导正确，half = 1ULL << (len - 1) 在 $len = 64$ 时算的是 $2^{63}$ ，也要求类型选对。这些细节正是后面公式法要绕开的。

子任务解法： $n \leqslant 10$

适用范围

$50\%$ 的数据满足 $n \leqslant 10$ 。此时 $2^n \leqslant 1024$ ，把整张表造出来只占很小的空间。

思路

完全按题目给出的三条规则模拟。从 $1$ 位格雷码开始，每推一层就把上一层的结果复制两份：

前一半保持原顺序，每个串前面补一个 0；
后一半逆序，每个串前面补一个 1。

推到第 $n$ 层，第 $k$ 个串就是答案。

代码

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/**
 * 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 20:28
 * update_at: 2026-10-01 20:28
 */
// subtask_50.cpp：50% 数据 n <= 10，按题意逐层生成完整的 2^n 个格雷码串。
// 从 1 位格雷码开始，每一层把上一层的串按原顺序补前缀 0、按逆序补前缀 1，
// 一直推到 n 位，再直接输出第 k 个。只有 n 很小、2^n 装得下时才可行。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;             // 编码位数，本文件只处理 n <= 10
ll k;              // 编号，50% 数据里 k < 2^10
vector<string> gray; // gray[i] = 当前这一层的第 i 个格雷码串

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

    cin >> n >> k;

    // 第 1 层：只有 "0" 和 "1"。
    gray.push_back("0");
    gray.push_back("1");

    // 每推一层，串的数量翻倍：前半段保持原顺序补 0，后半段逆序补 1。
    for (int len = 2; len <= n; len++) {
        int cnt = gray.size(); // 上一层共有 2^(len-1) 个串
        vector<string> cur;
        for (int i = 0; i < cnt; i++) {
            cur.push_back("0" + gray[i]); // 前半段：原顺序补 0
        }
        for (int i = cnt - 1; i >= 0; i--) {
            cur.push_back("1" + gray[i]); // 后半段：逆序补 1
        }
        gray = cur;
    }

    cout << gray[k] << '\n';

    return 0;
}

复杂度与瓶颈

第 $n$ 层有 $2^n$ 个长度为 $n$ 的串，时间和空间都是 $O(n \cdot 2^n)$ 。在 $n \leqslant 10$ 时轻松通过，但 $n = 64$ 时需要 $2^{64}$ 个串，连编号本身都存不下，整表生成彻底不可行。

子任务解法： $k \leqslant 5 \times 10^6$

适用范围

$80\%$ 的数据满足 $k \leqslant 5 \times 10^6$ 。这一档不再限制 $n$ ，转而限制编号本身的大小。

思路

观察格雷码相邻两个编号的关系。把 $n = 3$ 的格雷码和编号一起列出来：

编号 $k$	格雷码	相对上一个编号翻转的位
0	`000`	—
1	`001`	第 $0$ 位
2	`011`	第 $1$ 位
3	`010`	第 $0$ 位
4	`110`	第 $2$ 位
5	`111`	第 $0$ 位
6	`101`	第 $1$ 位
7	`100`	第 $0$ 位

第 $k$ 个串相对第 $k-1$ 个串翻转的那一位，正好是 $k$ 的最低非零二进制位，也就是 lowbit(k) = k & (-k)。编号 0 的格雷码是全 0，所以从编号 1 一路异或到编号 $k$ ，就得到了答案：

gray = \bigoplus_{i=1}^{k} \operatorname{lowbit}(i)

这一步把「生成所有串」换成了「在编号上走 $k$ 步」，不再依赖 $n$ ，也不需要存下任何串。

代码

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/**
 * 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 20:28
 * update_at: 2026-10-01 20:28
 */
// subtask_80.cpp：80% 数据 k <= 5*10^6，可以从 0 号串一步步推到 k 号串。
// 格雷码的相邻两个编号恰好只差一位：编号 i 的串由编号 i-1 的串翻转
// i 的最低位 1 对应的那一位得到。走 k 步即可，时间 O(k)，与 n 无关。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;    // 编码位数
ll k;     // 编号，本文件只处理 k <= 5*10^6
ll gray;  // 当前编号对应的格雷码数值

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

    cin >> n >> k;

    // 编号 0 的格雷码是全 0。
    gray = 0;

    // 从编号 1 推到编号 k：编号 i 相对 i-1 恰好翻转 lowbit(i) 这一位。
    for (ll i = 1; i <= k; i++) {
        ll low = i & (-i); // 取出 i 的最低非零二进制位
        gray ^= low;
    }

    // 从最高位到最低位输出，恰好 n 位，前导零也要输出。
    for (int bit = n - 1; bit >= 0; bit--) {
        cout << ((gray >> bit) & 1LL);
    }
    cout << '\n';

    return 0;
}

复杂度与瓶颈

时间 $O(k)$ ，空间 $O(1)$ 。 $k = 5 \times 10^6$ 时只需几千万次位运算，很快。但 $k$ 一旦达到 $2^{63}$ ，这个循环就跑不完；而且此时 $k$ 也快装不进有符号的 long long。

子任务解法： $k \leqslant 2^{63}-1$

适用范围

$95\%$ 的数据满足 $k \leqslant 2^{63}-1$ ，正好落在有符号 long long 的表示范围内。

思路

上面那个循环其实可以一步算完。把编号 $k$ 写成二进制：

text

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

两者异或，结果的第 $i$ 位是 $b[i+1] \oplus b[i]$ ，正好记录「编号的相邻两位是否不同」。连续翻转在异或里两两抵消，最后只剩一个变化位置，这正是格雷码相邻只差一位的来源。因此

gray = k \oplus (k \gg 1)

代码

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/**
 * 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 20:28
 * update_at: 2026-10-01 20:28
 */
// subtask_95.cpp：95% 数据 k <= 2^63-1，正好装进有符号 long long。
// 直接套二进制反射格雷码的公式 gray = k ^ (k >> 1)，时间 O(n)。
// 注意 k 最大是 2^63-1，它的最高位一定是 0，所以 gray 非负、有符号右移也安全；
// 再大一点（n = 64 时 k 可以到 2^64-1）就装不下了，需要 main.cpp 的无符号写法。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;    // 编码位数
ll k;     // 编号，0 <= k <= 2^63-1
ll gray;  // 编号 k 对应的格雷码数值

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

    cin >> n >> k;

    // 编号与右移一位的编号异或，得到的每一位表示「相邻两位是否不同」。
    gray = k ^ (k >> 1);

    // 从最高位到最低位输出，恰好 n 位，前导零也要输出。
    for (int bit = n - 1; bit >= 0; bit--) {
        cout << ((gray >> bit) & 1LL);
    }
    cout << '\n';

    return 0;
}

复杂度与瓶颈

时间降到 $O(n)$ ，空间 $O(1)$ 。公式本身没问题，剩下的唯一问题是 $k$ 的存储： $k$ 最大能到 $2^{63}-1$ ，此时它的最高位是 $0$ ，有符号 long long 刚好装得下；但 $n = 64$ 时 $k$ 可以取到 $2^{64}-1$ ，有符号整数就溢出了。

正解

关键观察

公式 $gray = k \oplus (k \gg 1)$ 对全部合法 $k$ 都成立，与 $n$ 的具体大小无关。所以 $100\%$ 数据和 $95\%$ 数据的算法完全相同，唯一区别是 $k$ 的类型。

$k$ 的取值上界是 $2^{64}-1$ ，超出有符号 long long 的最大值 $2^{63}-1$ 。解决办法不是强制转换，而是在声明时就把类型写对：编号和答案都用无符号 $64$ 位整数 unsigned long long。

思路

读入 $n$ 和 $k$ ；
计算 $gray = k \oplus (k \gg 1)$ ；
从第 $n-1$ 位输出到第 $0$ 位，恰好输出 $n$ 位。

第 3 步只做右移，不做左移，因此不会写出 1ULL << 64 这种未定义行为——这是本题最容易踩的边界。

代码

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/**
 * 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 20:28
 * update_at: 2026-10-01 20:28
 */
// main.cpp：满分做法，直接用二进制反射格雷码公式 gray = k ^ (k >> 1)。
// 时间 O(n)，空间 O(1)，是本题正式提交版本。
#include <bits/stdc++.h>
using namespace std;

// 本题 k 的上界是 2^64-1，超出有符号 long long 的范围，
// 所以编号和答案都用无符号 64 位整数，靠声明类型解决，不做任何强制转换。
typedef unsigned long long ull;

int n;    // 编码位数，1 <= n <= 64
ull k;    // 编号，0 <= k < 2^n
ull gray; // 编号 k 对应的格雷码数值

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

    cin >> n >> k;

    // 每一位表示「编号的相邻两位是否不同」，这正是格雷码的定义。
    gray = k ^ (k >> 1);

    // 从第 n-1 位输出到第 0 位，恰好 n 位，前导零也要输出。
    // n = 64 时最大只右移到第 63 位，不会出现 1ULL << 64 这种非法左移。
    for (int bit = n - 1; bit >= 0; bit--) {
        cout << ((gray >> bit) & 1ULL);
    }
    cout << '\n';

    return 0;
}

复杂度

时间复杂度： $O(n)$ ，只输出 $n$ 位。
空间复杂度： $O(1)$ ，只用常数个整数变量。

总结

整篇文章沿着「不断消掉存储与时间瓶颈」推进：

$50\%$ 档干脆把整张表造出来，瓶颈是 $2^n$ 个串；
$80\%$ 档改成在编号上一步步翻转，瓶颈变成 $k$ 次迭代；
$95\%$ 档用 $gray = k \oplus (k \gg 1)$ 把迭代压成一步，瓶颈变成 $k$ 的存储类型；
$100\%$ 档把 $k$ 和答案换成无符号 $64$ 位整数，补齐最后 $5\%$ 。

定义直译的递归定位不在这条链条上：它虽然也能过全部数据，但逆序下标和 $2^{63}$ 边界容易写错，只适合当作对照和对拍基准。

真正需要记住的只有一条公式和一条边界：公式是 $gray = k \oplus (k \gg 1)$ ，边界是 $n = 64$ 时不要计算 $2^n$ 、不要写 1ULL << 64，只输出已有整数的各个二进制位。

本文的 main.cpp 已用递归定义版 brute.cpp 进行 400 组随机对拍，覆盖 $1 \leqslant n \leqslant 64$ 的随机合法编号；三个分档代码也各自在其约束范围内对拍通过。

P5657 [CSP-S 2019] 格雷码

题目描述

通常，人们习惯将所有 $n$ 位二进制串按照字典序排列，例如所有 2 位二进制串按字典序从小到大排列为：00，01，10，11。

格雷码（Gray Code）是一种特殊的 $n$ 位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。

所有 2 位二进制串按格雷码排列的一个例子为：00，01，11，10。

$n$ 位格雷码不止一种，下面给出其中一种格雷码的生成算法：

1 位格雷码由两个 1 位二进制串组成，顺序为：0，1。
$n + 1$ 位格雷码的前 $2^n$ 个二进制串，可以由依此算法生成的 $n$ 位格雷码（总共 $2^n$ 个 $n$ 位二进制串）按顺序排列，再在每个串前加一个前缀 0 构成。
$n + 1$ 位格雷码的后 $2^n$ 个二进制串，可以由依此算法生成的 $n$ 位格雷码（总共 $2^n$ 个 $n$ 位二进制串）按逆序排列，再在每个串前加一个前缀 1 构成。

综上， $n + 1$ 位格雷码，由 $n$ 位格雷码的 $2^n$ 个二进制串按顺序排列再加前缀 0，和按逆序排列再加前缀 1 构成，共 $2^{n+1}$ 个二进制串。另外，对于 $n$ 位格雷码中的 $2^n$ 个二进制串，我们按上述算法得到的排列顺序将它们从 $0 \sim 2^n - 1$ 编号。

按该算法，2 位格雷码可以这样推出：

已知 1 位格雷码为 0，1。
前两个格雷码为 00，01。后两个格雷码为 11，10。合并得到 00，01，11，10，编号依次为 0 ~ 3。

同理，3 位格雷码可以这样推出：

已知 2 位格雷码为：00，01，11，10。
前四个格雷码为：000，001，011，010。后四个格雷码为：110，111，101，100。合并得到：000，001，011，010，110，111，101，100，编号依次为 0 ~ 7。

现在给出 $n$ ， $k$ ，请你求出按上述算法生成的 $n$ 位格雷码中的 $k$ 号二进制串。

输入格式

仅一行两个整数 $n$ ， $k$ ，意义见题目描述。

输出格式

仅一行一个 $n$ 位二进制串表示答案。

输入输出样例 #1

输入 #1

text

12 3

输出 #1

text

输入输出样例 #2

输入 #2

text

13 5

输出 #2

text

输入输出样例 #3

输入 #3

text

144 1145141919810

输出 #3

text

100011000111111010000001001001000000001100011

说明/提示

【样例 1 解释】

2 位格雷码为：00，01，11，10，编号从 0∼3，因此 3 号串是 10。

【样例 2 解释】

3 位格雷码为：000，001，011，010，110，111，101，100，编号从 0∼7，因此 5 号串是 111。

【数据范围】

对于 $50\%$ 的数据： $n \leq 10$

对于 $80\%$ 的数据： $k \leq 5 \times 10^6$

对于 $95\%$ 的数据： $k \leq 2^{63} - 1$

对于 $100\%$ 的数据： $1 \leq n \leq 64$ , $0 \leq k \lt 2^n$

[CSP-S 2019] 格雷码

目录

形式化题目

解法路线

暴力解法：按定义递归定位

适用范围

思路

代码

复杂度与瓶颈

子任务解法：n⩽10n \leqslant 10n⩽10

适用范围

思路

代码

复杂度与瓶颈

子任务解法：k⩽5×106k \leqslant 5 \times 10^6k⩽5×106

适用范围

思路

代码

复杂度与瓶颈

子任务解法：k⩽263−1k \leqslant 2^{63}-1k⩽263−1

适用范围

思路

代码

复杂度与瓶颈

正解

关键观察

思路

代码

复杂度

总结

子任务解法： $n \leqslant 10$

子任务解法： $k \leqslant 5 \times 10^6$

子任务解法： $k \leqslant 2^{63}-1$