[洛谷 5657][CSP-S2019]格雷码

题目链接

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$$

使用这种方法进行计算就可以避免很多溢出的问题了。

代码这里略去。