#include <iostream> using namespace std; typedef unsigned long long ull; ull n, k; void f(ull n, ull k) { if(n==1) { cout<<k; return; } ull mid = (1UL<<(n-1))-1; if(k<=mid) { cout<<0; f(n-1, k); } else { cout<<1; f(n-1, mid-k+mid+1); } } int main() { cin>>n>>k; f(n, k); cout<<endl; return 0; }

只解不答，不放代码，仅提供思路参考，可放心查看。 先说说评价，这题目好，有难度，就是样例3的输入太臭了 看题目有给数据范围，分很多层，想要拿满分的第一关： 2^63-1刚好是long long类型的数据范围，但会WA一个测试点，再一瞅k里头没负数，一眼看出请unsigned： 接下来分析思路，题目标签里面给了递归就按照递归写，递归函数参数至少需要俩，一个是当前位数，一个是在该位数下与当前位单位的0或1组合的位数-1位的格雷码编号，而递归边界给出了1位的格雷码0，1。 由于格雷码是二进制数，用字符数组、字符串一类的类型还是比较好的。 ========重难点来了======== 格雷码之所以可以使用递归，是因为它可以由固定规律的更少一位的格雷码与0或1以固定方式组合。 所以至少有 这种写法。 而难点在于这个固定规律中的“逆序”。 要分析这个“逆序”的规律，首先得分析“顺序”。以3位格雷码中的编号1格雷码为例。 递归的时候，因为编号1的格雷码在3位格雷码中的前2^2=4位，所以是编号为1的2位格雷码加前缀0。 以3位格雷码中的编号5格雷码做对比： 可以看到，因为编号5的格雷码在3位格雷码中的后2^2=4位，所以是编号为1的逆序2位格雷码加前缀1。 注意，前后组合的降1位格雷码的编号并没有变，变的是排序方式。而观察逆序状态下对应编号的格雷码，会发现它等同于顺序状态下的 格雷码最大编号-原编号 编号的格雷码。 得到了逆序格雷码编号与顺序格雷码编号的转换方法，就可以写出顺序和逆序状态下的两种递归返回： 自此，格雷码的重难点已经拆解完毕，相信你已经有了思路。 ========结语======== 怎么说呢，这题不算太难（我水平不高做得比较久），但是思路很有意思， 没有在题解区见到题解是令我感到奇怪的一件事。 想了想就自己写一篇算了，当作回顾思考总结。 end

考虑答案的每一位 第0位为011001100110... 第1位为0011110000111100... 发现第i位即k⊕[k/2]的第i位

实际上没必要递归 你实际上可以digui求出二进制其实没必要，注意用unsigned long long，否则你会WA一个

1. 首先明白题意,题的意思就是,生成n位的格雷码,然后有编号,求编号为k的那个二进制串(先放栈里面,然后放在bin里面就是二进制); 2. 此题通过上面的一堆文字分析可以得到一个规律,把k变为二进制,然后结果就是每一位和左边一位做异或操作(相等为0，不相等为1),当然此题也可以按照题目描述来做,依次确定每一位的字符,但本质上两种方法是一样的:,每一位只和自己和它左侧那一位的影响。 3. 比如输入的是3 5，那么会产生000，001，011，010，110，111，101，100，编号依次为 0 ~ 7，这八个二进制串，我们求编号为5的，也就是111；然后我们把k转为二进制即：0101，然后依次比较当前位和上一位（异或），可得一个串：111，就是想要输出的结果； 4. 需要判断需要是否要补前导0（因为有可能n>idx），所以需要在前面补0，样例3 3 通过规律得到的串为10，但是题目让输出n位，所以前面补n-idx个零，不然直接输出就是100，不对 5. 然后就是精度问题，题目上的k最大是2^64，所以要用ULL；LL就会一个点过不去； AC代码+注释

总共2n位组成的格雷码，前n位正序依次继承并在首位加0，后n位逆序继承并在首位加1，所以从当前k的值求出继承的编号。如2位编号3就可以通过观察发现继承的应该是1位编号0[2（父位格雷码总数）-(3（编号）+1（+1求序数）-2（子位格雷码半数）)] 以a代表父位格雷码总数或子位格雷码半数 化简即2*a-k-1 ！！！一定要开ULL，要不会WA很多！！！

简单位运算，唯一需要注意的是类型要是 unsigned long long，int和普通long long 装不下 代码：

#include<iostream> int n; unsigned long long k; int main(){ stdcin>>n>>k; k^=k>>1; while(~--n)stdcout<<(k>>n&1); }

为啥要用unsigned

n, k = map(int, input().split()) def gray_code(n, k): if n == 1: return str(k) if k < (1 << (n - 1)): return '0' + gray_code(n - 1, k) else: return '1' + gray_code(n - 1, (1 << n) - 1 - k) print(gray_code(n, k))

#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; int n, idx; ull k; int bin[100]; int ans[100]; stack<int> s; int main() { cin.tie(0); cin>>n>>k; while (k > 0) { s.push(k % 2); k /= 2; } while (!s.empty()) { bin[++idx] = s.top(); s.pop(); } for (int i = 1; i <= idx; ++i) { if (bin[i] == bin[i - 1]) { ans[i] = 0; } else { ans[i] = 1; } } for (int i = 1; i <= n - idx; ++i) { cout << 0; } for (int i = 1; i <= idx; ++i) { cout << ans[i]; } }

#include<iostream> int n; unsigned long long k; int main(){ stdcin>>n>>k; k^=k>>1; while(~--n)stdcout<<(k>>n&1); }

#include <iostream> using namespace std; typedef unsigned long long ull; ull n, k; void f(ull n, ull k) { if(n==1){ cout<<k; return; }ull mid = (1UL<<(n-1))-1; if(k<=mid) { cout<<0; f(n-1, k); } else { cout<<1; f(n-1, mid-k+mid+1); } } int main() { cin>>n>>k; f(n, k); cout<<endl; return 0; }

#include <iostream> #include <string> using namespace std; string grayCode(int n, unsigned long long k) { string res; for (int i = n - 1; i >= 0; --i) { if (k & (1ULL << i)) { res += '1'; k ^= (1ULL << i); if (i > 0) { k = (1ULL << i) - 1 - k; } } else { res += '0'; } } return res; } int main() { int n; unsigned long long k; cin >> n >> k; cout << grayCode(n, k) << endl; return 0; }