目录
显示
题目链接
https://www.luogu.org/problem/P5657
题解
方法一
题目中已经说清楚了格雷码的镜像构造法。
因此我们可以倒推,从高位到低位确定格雷码的每一位。
具体来说,我们设最低位为第 \(0\) 位。对于第 \(i\) 位,如果 \(k<2^i\),则该位为 \(0\)。否则该位为 \(1\),并令 \(k\) 的低 \(i+1\) 位全部反转。
实现时要注意可能的溢出问题。
#include <iostream> using namespace std; int main() { int n; unsigned long long k; cin>>n>>k; for(int i=n-1;i>=0;i--) { unsigned long long tmp=1ull<<i; if(k<tmp)cout<<'0'; else { cout<<'1'; k=(tmp<<1)-1-k; } } cout<<endl; return 0; }
方法二
OI-wiki 里提到了一种直接计算的方法。
$$G(k)=k\oplus \left\lfloor\frac{k}{2}\right\rfloor$$
使用这种方法进行计算就可以避免很多溢出的问题了。
代码这里略去。