题解：P5657 [CSP-S2019] 格雷码

wanghonghui123 · 2024-12-24 20:20:57 · 题解

思路

我们知道： G(k) = k \oplus \left( \frac{k}{2} \right) ，用位运算表示就是 k^(k>>1)。

• 我们可以先求出格雷码码值。

• 接着，我们可以把这个格雷码码值转化成二进制，并用 vector 数组存储。

• 由于是从最低位开始的，所以可以把 vector 数组反转或逆序输出即可。

注意：

• 由于数据很大，所以要开 unsigned long long。

• 为了长度为 n，即使高位时 0，也不要把需要前导零给去掉了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
vector<int> v;
int main(){
    int n;
    cin>>n;
    ULL k;
    cin>>k;
    ULL t = k^(k>>1);
    for(int i=0;i<n;i++){
        v.push_back((t&1)?1:0);
        t>>=1;
    }
    for(int i=v.size()-1;i>=0;i--){
        cout<<v[i];
    }
    return 0;
}