AcWing 1152 格雷码：递归与位运算解析

AcWing 1152 格雷码

题目描述

通常，人们习惯将所有 n 位二进制串按照字典序排列。格雷码（Gray Code）是一种特殊的 n 位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。

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

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

综上，n + 1 位格雷码，由 n 位格雷码的 2^n 个二进制串按顺序排列再加前缀 0，和按逆序排列再加前缀 1 构成，共 2^{n+1} 个二进制串。

对于 n 位格雷码中的 2^n 个二进制串，按上述算法得到的排列顺序将它们从 0 ~ 2^n - 1 编号。

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

输入输出

输入

仅一行，包含两个整数 n 和 k。

输出

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

样例

输入：

2 3 

输出：

10 

代码实现

#include<bits/stdc++.h>
using namespace std;

// 使用 unsigned long long，因为 k 可能很大（最大 2^64-1）
typedef unsigned long long ULL;

// 递归函数：查找 n 位格雷码中序号为 k 的格雷码
// 参数：n - 格雷码的位数，k - 要查找的格雷码序号（从 0 开始）
// 返回值：序号为 k 的 n 位格雷码的二进制字符串
string find(int n, ULL k){
    // 递归基：当 n=0 时，返回空字符串
    if (n == 0){
        return "";
    }
    // 计算 n 位格雷码总数的一半
    // 对于 n 位格雷码，总共有 2^n 个，一半是 2^(n-1) 个
    ULL len = (1ULL << (n - 1));
    
    // 情况 1：k 在前半部分（0 到 len-1）
    
     (k < len){
        
        
          + (n - , k);
    }  {
        
        
        
        
        
          + (n - , len *  -  - k);
    }
}

{
     n; 
    ULL k; 
    cin >> n >> k;
    
    cout << (n, k) << endl;
     ;
}