新手启示者
题目描述 Description
通常，人们习惯将所有 nn 位二进制串按照字典序排列，例如所有 22 位二进制串按字典序从小到大排列为：0000，0101，1010，1111。
格雷码（Gray Code）是一种特殊的 nn 位二进制串排列法，它要求相邻的两个二进制串间 恰好 有一位 不同，特别地，第一个串与最后一个串也算作相邻。
所有 22 位二进制串按格雷码排列的一个例子为：0000，0101，1111，1010。
nn 位格雷码不止一种，下面给出其中一种格雷码的生成算法：
- 11 位格雷码由两个 11 位二进制串组成，顺序为：00，11。
- n + 1n+1 位格雷码的前 2^n2n 个二进制串，可以由依此算法生成的 nn 位格雷码（总共 2^n2n 个 nn 位二进制串）按 顺序 排列，再在每个串前加一个前缀 00 构成。
- n + 1n+1 位格雷码的后 2^n2n 个二进制串，可以由依此算法生成的 nn 位格雷码（总共 2^n2n 个 nn 位二进制串）按 逆序 排列，再在每个串前加一个前缀 11 构成。
综上，n + 1n+1 位格雷码，由 nn 位格雷码的 2^n2n 个二进制串按顺序排列再加前缀 00，和按逆序排列再加前缀 11 构成，共2^{n+1}2n+1 个二进制串。另外，对于 nn 位格雷码中的 2^n2n 个二进制串，我们按上述算法得到的排列顺序将它们从 0 \sim 2^n - 10∼2n−1 编号。
按该算法，22 位格雷码可以这样推出：
- 已知 11 位格雷码为 00，11。
- 前两个格雷码为 0000，0101。后两个格雷码为 1111，1010。合并得到 0000，0101，1111，1010，编号依次为 0 \sim 30∼3。
同理，33 位格雷码可以这样推出：
- 已知 22 位格雷码为：0000，0101，1111，1010。
- 前四个格雷码为：000000，001001，011011，010010。后四个格雷码为：110110，111111，101101，100100。合并得到：000000，001001，011011，010010，110110，111111，101101，100100，编号依次为 0 \sim 70∼7。
现在给出 n, kn,k，请你求出按上述算法生成的 nn 位格雷码中的 kk 号二进制串。
输入描述 Input Description
从文件 code.in 中读入数据。
仅一行两个整数 n, kn,k，意义见题目描述。
输出描述 Output Description
输出到文件 code.out 中。
仅一行一个 nn 位二进制串表示答案。
样例输入 Sample Input
样例输入 1 2 3 样例输入2 3 5
样例输出 Sample Output
样例输出 1 10 样例输出 2 111
数据范围及提示 Data Size & Hint
样例说明 1
22 位格雷码为：0000，0101，1111，1010，编号从 0 \sim 30∼3，因此 33 号串是1010。
样例说明 2
33 位格雷码为：000000，001001，011011，010010，110110，111111，101101，100100，编号从 0 \sim 70∼7，因此55 号串是 111111。
对于 50\%50% 的数据：n \le 10n≤10；
对于 80\%80% 的数据：k \le 5 \times 10^6k≤5×106；
对于 95\%95% 的数据：k \le 2^{63} − 1；
对于 100\%100% 的数据：1 \le n \le 64 , 0 \le k < 2^n1≤n≤64,0≤k<2n。
@谭迪元@张帆@汪恺恒@酷町猫@赵逸凡
汪宇航在2021-03-19 18:10:59追加了内容
跪拜大佬，不，跪拜巨佬！！！！！！！！！！！
初级光能
找到规律就简单了
标准gray code还有一种求法，就是将转成二进制，结果就是每一位和左边一位做异或操作。当然此题也可以按照题目描述来做，依次确定每一位的字符，但本质上两种方法是一样的：每一位只受自己和它左侧那一位的影响。
核心
while(k) temp[++tot]=k%2,k/=2;转二进制之后统计
for(int i=1;i<=n;i++){
if(temp[i+1]==temp[i]) ans[i]='0';
else ans[i]='1';
}最后逆序输出ans数组就行了
注意变量要用unsigned long long定义！否则WA91
新手启示者
顶！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
新手启示者
#include <bits/stdc++.h>
using namespace std;
int main(){
string ans;
int n,k,temp[1000000],tot;
cin>>n>>k;
while(k){
temp[++tot]=k%2,k/=2;
}
for(int i=1;i<=n;i++){
if(temp[i+1]==temp[i]){
ans[i]='0';
}else{
ans[i]='1';
}
}
for(int i=n;i>=0;i--){
cout<<ans[i];
}
return 0;
}
66????????
新手启示者
#include <bits/stdc++.h>
using namespace std;
int main(){
string ans;
unsigned long long n,k,temp[1000000],tot;
cin>>n>>k;
while(k){
temp[++tot]=k%2,k/=2;
}
for(int i=1;i<=n;i++){
if(temp[i+1]==temp[i]){
ans[i]='0';
}else{
ans[i]='1';
}
}
for(int i=n;i>=0;i--){
cout<<ans[i];
}
return 0;
}
91...........
