yltx's blog

yltx's blog

Κοιτάζοντας πάνω στον έναστρο ουρανό, κάτω στη γη.

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

posted on 2019-11-16 17:51:03 | under 题解 |

唯一可做题?

0.5h写完。

但是一看 $n\le64$ ,而众所周知这个 $2^{64}$ 是爆long long的。

于是想到了ull。

但计算过程中发现 $1ll<<64$ 会有一些奇怪的问题,于是我们压到 $2^{63}$ 。

思路:

分治,设当前是 $nn$ 位格雷码中的第 $nk$ 个,则当 $nk>\frac{2^{nn}}{2}$ 的时候需要将 $nk$ 转为 $2^{nn}-nk-1$ ,否则保留不动。

由于 $2^{nn}$ 会爆long long,所以我们只能将 $nk$ 换个表示方式: $2^{nn-1}-(nk-(2^{nn-1}))-1$ 。

于是代码就出来了:

#include<bits/stdc++.h>
using namespace std;
long long n;
unsigned long long k;
string a[5]={"0","1"};
string dfs(int nn,unsigned long long nk){
    if(nn==1)return a[nk];
    string ans;
    if(nk>=(1ll<<(nn-1)))ans='1'+dfs(nn-1,(1ll<<(nn-1))-(nk-(1ll<<(nn-1)))-1);//后半部分
    else ans='0'+dfs(nn-1,nk);//前半部分
    //依题意生成第nk个nn位格雷码,返回
    return ans;
}
int main(){
    cin>>n>>k;
    cout<<dfs(n,k);
}