2019 格雷码 · 方案一递归构造

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 2/5 · 共 1181 字

n 位格雷码中第 k 个（k 从 0 开始）01 串

2019
位运算

正文

// CSP-S 2019 复赛 T1 · 格雷码（方案一：递归构造）
// 原题：https://oj.yecheng.tv/p/CSPS2019A
// 题意：n 位格雷码中第 k 个（k 从 0 开始）01 串。构造规则：G(n) 的
//       前 2^(n-1) 个是 0 + G(n-1)，后一半是 1 + reverse(G(n-1))。
// 思路（分治递归）：
//   设 solve(n, k) 输出 n 位格雷码第 k 个的首位并递归：
//   - n == 0：结束；
//   - 若 k < 2^(n-1)：首位 0，递归 solve(n-1, k)；
//   - 否则首位 1，递归 solve(n-1, 2^n - 1 - k)（后半是反转的前半，
//     所以"倒着数"第 2^n - 1 - k 个）。
//   n ≤ 64，k 最大 2^64 - 1，必须用 unsigned long long。
// 复杂度：O(n)。
// 易错点：
//   1. k 用 %llu 读入，移位写 1ULL << (n-1)；
//   2. 倒数下标公式 (2^n - 1) - k 直接照题面递归写，别手推变形；
//   3. 输出就是 01 串本身，无多余分隔符。
#include <cstdio>

void solve(int n, unsigned long long k, char* buf, int& pos) {
    if (n == 0) return;
    unsigned long long half = 1ULL << (n - 1);
    if (k < half) {
        buf[pos++] = '0';
        solve(n - 1, k, buf, pos);
    } else {
        buf[pos++] = '1';
        solve(n - 1, (half << 1) - 1 - k, buf, pos);
    }
}

int main() {
    freopen("code.in", "r", stdin);
    freopen("code.out", "w", stdout);
    int n;
    unsigned long long k;
    scanf("%d%llu", &n, &k);
    static char buf[70];
    int pos = 0;
    solve(n, k, buf, pos);
    buf[pos] = '\0';
    printf("%s\n", buf);
    return 0;
}

2019 格雷码 · 方案一 递归构造

正文

CSP-S 标程 · 复赛真题的其它内容

2019 格雷码 · 方案一递归构造