题解 P5657 【格雷码【民间数据】】
引领天下
2019-11-16 17:51:03
唯一可做题？
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$。
于是代码就出来了：
```cpp
#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);
}
```