【解题报告】洛谷P5657 格雷码

题目链接

https://www.luogu.com.cn/problem/P5657

思路

我们大眼观察数据

然后发现， nn 位格雷码实际上是由 n−1n-1 位格雷码转化而来

找规律知道，除去第一位之外，前一半和后一半的数值实际上是中心对称的，所以我们打出了如下的暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
unsigned long long n,k;
void dfs(unsigned long long n,unsigned long long k)
{
	if(n==0)
	return ;
	long long x=(1<<(n-1));//表示有多少个
	if(k==0)//如果k为0的话，没有好吧
	{
		for(long long i=1;i<=n;i++)
		cout<<"0";
		return ;
	}
	if(k+1>x)//如果要的数字在中间的右边
	{
		long long next=2*x-k-1;//计算对应右边的n-1位格雷码
		cout<<"1";
		dfs(n-1,next);
	}
	else//在左边就是正常的格雷码
	{
		long long next=k;
		cout<<"0";
		dfs(n-1,next);
	}
}
int main()
{
	//freopen("code.in","r",stdin);
	//freopen("code.out","w",stdout);
	cin>>n>>k;
	dfs(n,k);
	cout<<endl;
//	fclose(stdin);
 //	fclose(stdout); 
	return 0;
}

这份代码可以得到60pts的高分

所以我们继续研究

分别把自己能手算出来的每个格雷码和 kk 进行对比发现

当 k≥2k\ge 2 的时候，第 kk 个格雷码的第 11 位是 k−2k-2 的第二位去翻的结果，否则格雷码的第一位是 00

实际上还有更方便的方法

考虑答案的每一位，发现格雷码第 ii 位是 k xor ⌊k2⌋k \space xor \space \lfloor \dfrac k 2 \rfloor 的第 ii 位

然后。。。就过了？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
int n;
unsigned long long k;
int main()
{
	cin>>n>>k;
	k^=k>>1;
	while(~--n)
	cout<<(k>>n&1);
	return 0;
}