z3475 的博客

题解 P5657 【格雷码【民间数据】】

题目已经描述了构造方法,就着写就可以了

值得注意的是要注意越界(64位记得开unsigned long long,但是unsigned long long也不能表示$2^{64}$)

只需要把$$ 2^n-1-k $$ 换成$$ 2^{n-1}-1-(k-2^{n-1}) $$ 即可

#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;

string getb(int n,ll k){
    ll mid=1ull<<(n-1);
    if (n==0) return "";
    if (k<mid)
        return "0"+getb(n-1,k);
    else
        return "1"+getb(n-1,mid-1-(k-mid));
}
int main(){
    int n;ll k;
    cin>>n>>k;
    cout<<getb(n,k);
}

2019-11-16 16:55:39 in 题解