题目传送门：P5657 [CSP-S2019] 格雷码

本题可以用于练习分治。

做题

我们用 $n$ 表示当前生成格雷码的位数为 $2^n$，$k$ 表示要生成的是这 $2^n$ 个格雷码的第 $k$ 个。则如果 $k$ 属于前一半即 $k < \dfrac{2^n}{2}$，则该位输出 $0$，否则该位输出 $1$。

那后一半的位怎么求呢？题目给出，对于后一半的格雷码是逆序排列的。所以如果当前 $k$ 是 $2^n$ 的后一半则分治时将它变到对称的前一半去，可以解决逆序的问题。

也就是，对于长度为 $2^n$ 的第 $k$ 种格雷码函数 $f(n,k)$：

• （如果 $n=0$，返回）

• 如果 $k < 2^{n-1}$，则输出 $0$，并分治 $f(n-1,k)$；

• 否则 $k$ 在后一半，输出 $1$ 并分治 $f(n-1,2^n - k)$。

代码

记得开合适的类型。

递归：

#include<bits/stdc++.h>
using namespace std;
string calc(int n,__int128 k)
{
    if(n==1)return k ? "1" : "0" ;
    __int128 s= __int128(1)<<n;
    
    if(k>=s/2) return "1"+calc(n-1,s-1-k);
    else       return "0"+calc(n-1,k);
}

int main()
{
    int n;unsigned long long k;
    cin>>n>>k;
    cout<<calc(n,k);
    return 0;
}

公式：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;unsigned long long k;
    cin>>n>>k;
    k=k ^ (k>>1);
    bitset<64>B = k;
    for(int i=n-1;i>=0;i--)printf("%d",(B[i]==1));
    return 0;
}