P5657 题解

ikunTLE · 2024-12-24 18:42:29 · 题解

题目传送门

思路

格雷码最大的特点是，对于 x 与 x+1 的二进制最多有一位不同。对比格雷码和二进制，对于第 i 为格雷码为 1 的情况，仅当二进制下第 i 位与第 i+1 位不同时。

这种运算可以用看作是异或运算，故 k 的格雷码是 k\oplus\lfloor\frac{k}{2}\rfloor。最后转成二进制输出即可。

注意事项

AC CODE

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

int main(){
    int n;
    scanf("%d",&n);
    unsigned long long k;//注意数据范围
    scanf("%llu",&k);
    k^=k>>1;//转为格雷码
    while(n){
        printf("%llu",(k>>(n-1))&1);//输出二进制
        --n;//转到下一位
    }
    printf("\n");
    return 0;
}