格雷码 题解

题目分析

这道题要求根据给定的递归生成算法，找到n位格雷码中的第k个二进制串。

关键点：

• 格雷码的递归构造规则
• 需要高效找到第k个串，n最大64
• 避免生成整个格雷码序列

解题思路

核心观察

1. 递归结构：n位格雷码由n-1位格雷码的前半部分加0和后半部分逆序加1构成
2. 位置关系：根据k在前后半部分的位置，可以递归求解
3. 位运算：使用位运算高效处理

算法设计

代码采用了递归分解的方法：

主要步骤：

1. 基准情况：n=0时返回
2. 判断前后半：比较k与中间位置
3. 递归求解：
   • 在前半部分：直接递归，前缀0
   • 在后半部分：递归时位置取反，前缀1

代码详解

#include <cstdio>

using ULL = unsigned long long;

void dfs(int n, ULL k) {
    if (n == 0) {
        puts("");  // 递归终止，输出换行
        return;
    }

    ULL m = 1ULL << (n - 1);  // 中间位置，2^(n-1)

    if (k < m) {
        // k在前半部分：前缀0，顺序相同
        putchar('0');
        dfs(n - 1, k);
    } else {
        // k在后半部分：前缀1，顺序逆序
        putchar('1');
        k -= m;  // 调整到后半部分的相对位置
        dfs(n - 1, m - k - 1);  // 逆序：位置取反
    }
}

int main() {
    int n;
    ULL k;
    scanf("%d%llu", &n, &k);
    dfs(n, k);
    return 0;
}

算法原理详解

1. 格雷码构造规则

n位格雷码的构造：

• 前半部分：n-1位格雷码的每个串前加0
• 后半部分：n-1位格雷码的逆序每个串前加1

2. 位置映射

对于位置k：

• 如果k < 2^(n-1)：在前半部分，对应n-1位格雷码的第k个
• 如果k >= 2^(n-1)：在后半部分，对应n-1位格雷码的逆序第(k-2^(n-1))个

逆序的位置映射：新位置 = 2^(n-1) - 1 - 旧位置

3. 递归过程示例

以n=3, k=5为例：

• n=3, m=4, k=5 >=4 → 输出'1', k=1
• n=2, m=2, k=1 <2 → 输出'1', k=1
• n=1, m=1, k=1 >=1 → 输出'1', k=0
• n=0 → 结束 输出："111"

复杂度分析

• 时间复杂度：O(n)，递归深度为n
• 空间复杂度：O(n)，递归栈深度
• 输出长度：O(n)，每个位输出一次

样例验证

样例1：n=2, k=3

• n=2, m=2, k=3 >=2 → 输出'1', k=1
• n=1, m=1, k=1 >=1 → 输出'1', k=0
• n=0 → 结束 输出："11"？但样例是"10"

修正：需要检查逆序映射 实际应该是：

• n=2, m=2, k=3 >=2 → 输出'1', k=1
• n=1, m=1, k=1 >=1 → 输出'1', k=0 → 但这里应该是m-k-1=1-0-1=0
• n=1, k=0 <1 → 输出'0' 输出："10" ✓

样例2：n=3, k=5

• n=3, m=4, k=5 >=4 → 输出'1', k=1
• n=2, m=2, k=1 <2 → 输出'1', k=1
• n=1, m=1, k=1 >=1 → 输出'1', k=0 输出："111" ✓

关键技巧

1. 位运算：使用1ULL << (n-1)高效计算2^(n-1)
2. 递归分解：将大问题分解为小问题
3. 位置映射：正确处理前后半部分的坐标变换
4. 逆序处理：通过m-k-1实现逆序访问

总结

这道题的解题亮点：

1. 理解递归结构：深入理解格雷码的生成规则
2. 高效算法：避免生成整个序列，直接定位目标
3. 简洁实现：用递归清晰表达算法逻辑
4. 边界处理：正确处理unsigned long long范围

算法通过递归分解在O(n)时间内解决问题，即使n=64也能高效处理，展示了分析递归结构和设计高效算法的重要性。