[CSP-S2019]格雷码题解

CSP-S2 2019 D1T1

考场上第一遍读题的时候感觉不是很一眼……不是很符合D1T1的气质

之前完全没听说过格雷码是什么玩意，还是我太菜了

仔细读题后发现应该是有规律可循的

赛后据说有$O(1)$算法，反正我不会

思路分析

写出一些小位数的格雷码全排列，再根据格雷码的生成算法，可以有以下算法：

1. 对于$x$位第$k$个格雷码，若$k\geq2^{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=;

    while(b)

    {

        if(b&)

            ans*=a;

        b>>=;

        a*=a;

    }

    return ans;

}

int main()

{

    scanf("%d",&n);cin>>k;

    for(int i=n-;i>=;i--)

    {

        ull now=fastpow(,i);

        if(k<now)

            printf("");

        else

            printf(""),k=*now-k-;

    }

    return ;

}

巴特西

[CSP-S2019]格雷码题解

最新文章

热门文章

巴特西

[CSP-S2019]格雷码 题解

最新文章

热门文章

[CSP-S2019]格雷码题解