模拟？× 找规律？√

首先，我们观察题目给出的一组格雷数： 000 001 011 010 110 111 101 100

会惊奇地发现， 前四个格雷数的第一位都为0 （000，001，011，010） 数字的加粗得好像不是很明显； 后四个格雷数的第一位都为1 （110，111，101，100） 数字的加粗得不是很明显2.0；

然后，我们把这组格雷数从中间分开，前四个格雷数放一起，后四个格雷数放一起

继续看，又会惊奇地发现：

1. 前半部分： 前两个数的第二位都是0（000，001），设这组格雷数为 a； 后两个数串的第二位都是1（011，010），设这组格雷数为 b；

• 二分 a（00​0​，00​1​） 前一个数的第三位都是0 （即前半部分）； 后一个数的第三位都是1 （即后半部分）；
• 二分 b（01​1​，01​0​） 前一个数的第三位都是1 （即前半部分）； 后一个数的第三位都是0 （即后半部分）；

2. 后半部分： 前两个数的第二位都是1（110，111），设这组格雷数为 c； 后两个数的第二位都是0（101，100），设这组格雷数为 d；

• 二分 c（11​0​，11​1​） 前一个数的第三位都是0 （即前半部分）； 后一个数的第三位都是1 （即后半部分）；
• 二分 d（10​1​，10​0​） 前一个数的第三位都是1 （即前半部分）； 后一个数的第三位都是0 （即后半部分）；

我们理一下思路，就会发现：

【划重点！！！】每一阶段前半部分或后半部分二分次数对应的位数是 0 还是 1 取决于上一个阶段，也就是看 k 在上一阶段是在前半部分还是后半部分

#1. 上一阶段在前半部分，

• 这一阶段前半部分对应位数的字符是0
• 这一阶段后半部分对应位数的字符是1

#2. 上一阶段在后半部分，

• 这一阶段前半部分对应位数的字符是1
• 这一阶段后半部分对应位数的字符是0

可以在处理的过程中直接输出，不需要存储。

还有一点！！ 一定要使用 unsigned long long !!!!!!

CODE:

#include<cstdio>
#include<cmath>
using namespace std;

int n;
unsigned long long k;

int main(){
	/* 几天前刚刚在某本编程书上看到的，现学现用()() 
	long long：有符号长整数类型，存储范围 [-2^63, 2^63-1]
	unsigned long long：无符号长整数类型，存储范围 [0, 2^64-1] 
	*/
    scanf("%d%llu", &n, &k);  //%llu：存储 unsigned long long 类型输入（%lld 只能存储 long long 类型输入，超出范围时会对 2^63 取模） 

    bool flag=0;  //标记 k 是否为后一半数据 
    while(n--){  //输出位数 == n 
    	unsigned long long t=pow(2, n);  //这里必须用 unsigned long long 类型变量存储一下，否则最大只能存储 long long 类型范围的数据 
        if(k < t){  //k 为前一半数据
            if(flag) printf("1");
            else printf("0");

            flag = 0;
        } else{  //k 为后一半数据 
            if(flag) printf("0");
            else printf("1");

            k -= t;
            flag = 1;
        }
    }
    printf("\n");

    return 0;
}

详情见宋昊哲解析（题解很好可直接COPY）