2019 格雷码 · 方案二异或公式

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

格雷码封闭形式 G(k) = k XOR (k>>1)，一步输出

2019
位运算

正文

// CSP-S 2019 复赛 T1 · 格雷码（方案二：异或公式一步到位）
// 原题：https://oj.yecheng.tv/p/CSPS2019A
// 题意：同方案一。
// 思路（格雷码封闭形式）：
//   格雷码有一个著名公式：G(k) = k XOR (k >> 1)。
//   正确性直觉：相邻整数 k 与 k+1 异或 (k+1)>>1 后恰好只差一位，
//   且首项为 0；可用 n=3 手算全表验证与递归定义一致。
//   于是答案 = (k ^ (k >> 1)) 按二进制输出、高位补 0 到 n 位。
// 复杂度：O(n)，常数比递归版更小。
// 易错点：
//   1. 必须补足前导 0（k 小时高位全是 0），从第 n-1 位倒着输出；
//   2. 移位用 1ULL 防溢出；读入 k 用 %llu；
//   3. k = 2^n - 1 时 k>>1 不溢出，无需特判。
#include <cstdio>

int main() {
    freopen("code.in", "r", stdin);
    freopen("code.out", "w", stdout);
    int n;
    unsigned long long k;
    scanf("%d%llu", &n, &k);
    unsigned long long g = k ^ (k >> 1);
    for (int i = n - 1; i >= 0; i--) {
        putchar(((g >> i) & 1ULL) ? '1' : '0');
    }
    putchar('\n');
    return 0;
}

2019 格雷码 · 方案二 异或公式

正文

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

2019 格雷码 · 方案二异或公式