复赛一：格雷码(grad code)

洛谷：5657
OJ: CSPS2019A

原理解释

根据题目描述的递推构造法：

1. n 位格雷码前一半是 n−1 位格雷码加前缀 0；
2. 后一半是 n−1 位格雷码的逆序加前缀 1。

这个构造出来的序列，恰好就是标准二进制反射格雷码（Binary Reflected Gray Code）。
而这个格雷码的数学生成公式就是：\([\text{Gray}(k) = k \oplus (k >> 1)]\)

它的逆运算（如果你想从格雷码求原编号）是：\([k = g \oplus (g >> 1) \oplus (g >> 2) \oplus \dots]\)

🔢 举例验证

对应题目 2 位格雷码的排列正是：

00, 01, 11, 10

完美匹配。

结论

是的，g = k ^ (k >> 1) 这个公式不仅能用，而且是标准、快速、通用的格雷码生成方法。
它可以直接用于任意 n 位格雷码题目，无需递归构造。

取第i位操作

(g >> i) & 1ULL
它是 C/C++ 位运算 中非常常见的“取某一位”的写法。假设我们有一个无符号整数 g（例如格雷码结果）。我们想取出 g 的第 i 位（二进制位）。

① (g >> i)
👉 表示将 g 右移 i 位。
也就是把第 i 位移到最低位（第 0 位）。

例如：

g = 110110 (二进制)
i = 2
g >> 2 = 1101

原来的第 2 位移到了末尾位置）

② & 1ULL

👉 & 是按位与（bitwise AND）运算。
1ULL 表示一个 值为 1 的无符号长整型常量（unsigned long long）。

1ULL 的二进制形式是：

...00000001

按位与的规则：

• 如果最低位是 1，则结果为 1；
• 否则为 0。

所以 (g >> i) & 1ULL 的作用是：

取出 g 的第 i 位（二进制位），结果是 0 或 1。

举个例子

假设：

unsigned long long g = 0b101011; // 十进制 43

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-10-05 21:20:23
 * 最后修改: 2025-10-05 21:47:58
 * 文件描述: 【19CSPS提高组】格雷码
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;                // 位数
    unsigned long long k;       // 第 k 个（从 0 开始）
    if (!(cin >> n >> k)) return 0;

    unsigned long long g = k ^ (k >> 1); // k 的格雷码
    // 输出为 n 位二进制串（高位在前，补前导 0）
    for (long long i = n - 1; i >= 0; --i) {
        cout << ((g >> i) & 1ULL);
    }
    return 0;
}