【CSP2019】格雷码 | Mrsrz's blog

模拟

题目大意：

求 $n$ 位格雷码中第 $k$ 个。

题解：

按题意一位一位确定即可。

发现去掉一位以后，前一半反一下就是后一半，所以直接递归即可。

时间复杂度 $O(n)$。

注意 $2^{64}-1$ 要unsigned long long，然后输入要用llu，左移的时候要1uLL<<(n-1)等否则会挂。

Code：

#include<cstdio>
using namespace std;
typedef unsigned long long LL;
int n;LL k;
LL solve(int n,LL k){
    if(n==0)return k;
    const LL mid=1uLL<<n;
    if(k<mid)return solve(n-1,k);else
    return 1uLL<<n|solve(n-1,mid*2-k-1);
}
int main(){
    scanf("%d%llu",&n,&k);
    LL ans=solve(n-1,k);
    for(int i=n-1;~i;--i)
    printf("%lld",ans>>i&1);
    printf("\n");
    return 0;
}

---

事实上是有更好的解法的。

发现答案为k^(k>>1)。

所以就有一份 $56\rm B$ 的代码（by yhx）……

n,k=map(int,input().split());print(bin(1<<n|k^k>>1)[3:])