专栏文章

题解：P5657 [CSP-S2019] 格雷码

wwanghonghui123
P5657题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqo7pg9
此快照首次捕获于
2025/12/04 08:01
3 个月前
此快照最后确认于
2025/12/04 08:01
3 个月前
查看原文

思路

我们知道：G(k)=k⊕(k2)G(k) = k \oplus \left( \frac{k}{2} \right)，用位运算表示就是 k^(k>>1)。
  • 我们可以先求出格雷码码值。
  • 接着，我们可以把这个格雷码码值转化成二进制，并用 vector 数组存储。
  • 由于是从最低位开始的，所以可以把 vector 数组反转或逆序输出即可。
注意：
  • 由于数据很大，所以要开 unsigned long long。
  • 为了长度为 nn，即使高位时 00，也不要把需要前导零给去掉了。

代码

CPP
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
vector<int> v;
int main(){
	int n;
	cin>>n;
	ULL k;
	cin>>k;
	ULL t = k^(k>>1);
	for(int i=0;i<n;i++){
		v.push_back((t&1)?1:0);
		t>>=1;
	}
	for(int i=v.size()-1;i>=0;i--){
		cout<<v[i];
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...