[CSP-S2019]格雷码 题解
CSP-S2 2019 D1T1
考场上第一遍读题的时候感觉不是很一眼……不是很符合D1T1的气质
之前完全没听说过格雷码是什么玩意，还是我太菜了
仔细读题后发现应该是有规律可循的
赛后据说有$O(1)$算法，反正我不会
思路分析
写出一些小位数的格雷码全排列，再根据格雷码的生成算法，可以有以下算法：
1. 对于$x$位第$k$个格雷码，若$kgeq2^{x-1}$，则显然该格雷码是由$x-1$位的第$2^{x-1}-(k-2^{x-1}+1)=2^x-k-1$个格雷码前面加上一个1得来的；否则，该格雷码是由$x-1$位的第$k$个格雷码前面加上一个0得来的
1. 重复步骤1，直到$x=0$。
具体实现
模拟即可，可以边模拟边输出。
看一眼数据范围，特地提示了$5$分的$unsigned$ $long$ $long$。。。所以记得开
求幂的时候也要注意精度问题，可以使用快速幂
#include<iostream> #include<cstdio> #define ull unsigned long long using namespace std; int n; ull k; ull fastpow(ull a,ull b) { ull ans=1; while(b) { if(b&1) ans*=a; b>>=1; a*=a; } return ans; } int main() { scanf("%d",&n);cin>>k; for(int i=n-1;i>=0;i--) { ull now=fastpow(2,i); if(k<now) printf("0"); else printf("1"),k=2*now-k-1; } return 0; }