CSP2019题解D1T1格雷码
地铁dixiatielu
2020-01-19 12:31:35
# CSP2019题解
# D1T1
## 格雷码
作者：（地铁DXTL）
对于这道题，首先，不难想出开一个比较大的数组，把从1到n的所有二进制格雷码全部以字符串的形式存下来。看看数据范围：
如果我们使用开数组，把所有的格雷码存起来的方法，需要开大小为的String数组，明显会MLE。
这个时候，我们发现格雷码一定是小于的一个二进制数字。并且题目并不是要求我们输出每个格雷码，而只是要求了输出n位格雷码中的第k个。所以我们容易想到类似状压的一种方法，先把二进制字符串转成十进制，然后再递归地去运行程序，输出答案。
通过观察题目所给样例，我们发现n位格雷码总共有个，而前一半都是以0开头，后一半都是以1开头。因此我们可以写一个递归处理的函数，每一层代表正在把此题当作一个叫做"输出n位格雷码的第k个格雷码"的问题来做。
(代码里有详细的解释)
上代码qwq
```cpp
#include <cstdio>
#define reg register
#define IL inline
using namespace std;
int n;
unsigned long long k,stt = 1;
IL void work(unsigned long long cur)//cur表示当前处理的这一层的格雷码总数
{
if(cur == 2)//递归边界，当当前数值为2的1次方的时候达到边界
{
putchar(k == 1 ? '0' : '1');//看看k是1还是2，如果是第一个就是0，如果是第二个就是1
return;//结束程序
}
if(k <= (cur >> 1))//判定一下他要我们求的第k个格雷码在这层格雷码总数的前一半还是后一半
{
putchar('0');//如果是前一半，则直接输出0，这个k值还能继续用。
}
else
{
k = cur - k + 1;//如果在后一半里，那么显然k值大于下一层的格雷码总数。因此得把k值处理一下。对于下一层来说，由于后一半是逆序排列的，则要求的k值就是现在这一层格雷码总数减去k再+1（此处无法理解可以多思考一下）
putchar('1');//输出1
}
work(cur >> 1);//递归继续处理
}
int main()
{
scanf("%d%llu",&n,&k);//读入，注意unsigned long long用%llu读入
if(!k)//当时考场上打的，以防万一，特判了一个k=0的情况，也就是全是0的情况，当然把这一段删了也没问题
{
for(reg int i = 1;i <= n;i++)
{
putchar('0');
}
return 0;
}
if(n == 64)
{
n--;//接下来我们可以把n当作63看，然后递归处理。由于unsigned long long最大存2的64次方-1，所以这里需要特判n=64的情况
if(k < 9223372036854775808)//9223372036854775808是2的63次方
{
putchar('0');
}
else//同上work函数
{
putchar('1');
k = 9223372036854775808 - k;
k += 9223372036854775808;//为了防止unsigned long long炸掉，就先减了再加。本来应该是k=9223372036854775808 * 2 - k的
}
}
else//如果不是n=63的话
k++;//就把k++（我是把格雷码的序号当作1到n看的，与题目中的0~n-1不同）
for(reg int i = 1;i <= n;i++)
{
stt <<= 1;
}
work(stt);//这里传参数如果直接传1<<n会出一些奇怪的毛病，我也不知道为什么，所以就只能这样了。
putchar('\n');
return 0;
}
```