NOIP2019 D1T1 格雷码

题目链接：https://www.luogu.com.cn/problem/P5657

这个题可以看成是一个找规律的题目，每一位的0/1都是由k在区间内的左还是右所决定的。用flag记录k位于上一段的左边/右边。

如果上一段在左边，那么左右遵循0，1；如果上一段在右边，那么左右遵循1，0。

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #define ull unsigned long long
 5 using namespace std;
 6 int flag;
 7 int main(){
 8     int n;
 9     ull k,t;
10     cin>>n>>k;
11     t=pow(2,n-1);
12     while(t){
13         if(!flag){//上一段左边 
14             if(k<t) {cout<<0;flag=0;}
15             else{cout<<1;k-=t;flag=1;}//这一段在右边
16         }
17         else{
18             if(k<t) {cout<<1;flag=0;}
19             else{cout<<0;k-=t;flag=1;}
20         }
21         t=t>>1;
22     }
23     return 0;
24 }

AC代码