Apocalypse Someday

定义一个数是合法的，当且仅当中间出现至少一个连续的大于三个的6,求第x个合法的数，\(x\leq 50,000,000\)

解

首先，注意到求第几个，即想到试填法，而试填法关键在于确定了这个状态下的方案数，记住这个，接下来就很好理解了。

显然要表现长度，又因为要表现合法，于是设\(f[i][j]\)表示有i位的数，状态为j(0表示最高位没有6,1有1个6,2表示有连续的两个6的不合法的数,3表示这是一个合法的数)的方案数，因此不难有

\[f[i][0]=(f[i-1][0]+f[i-1][1]+f[i-1][2])\times 9
\]

\[f[i][1]=f[i-1][0],f[i][2]=f[i-1][1],f[i][3]=10\times f[i-1][3]+f[i-1][2]
\]

边界：\(f[0][0]=1\)

于是我们可以以此从高位到低位进行试填，数字从小到大，注意特判6,比如填到第i位，此处填了一个6,前面有2个连续的6紧挨着第i位，于是不但\(f[i-1][3]\)为合法的方案，还有\(f[i-1][1]+f[i-1][2]\)，同理可推出前面有1个6,注意前面3个6时，不管这里填什么，方案都是\(f[i-1][0]+f[i-1][1]+f[i-1][2]+f[i-1][3]\)

#include <iostream>

#include <cstdio>

#define il inline

#define ri register

#define int long long

using namespace std;

int dp[21][4];

il int max(int,int);

il void read(int&),prepare();

main(){

    int lsy;read(lsy),prepare();

    while(lsy--){

        int x;read(x);

        int w(0),i,j,t6(0),cnt;

        while(dp[w][3]<x)++w;

        while(w){

            for(i=0;i<10;++i){

                cnt=dp[w-1][3];

                if(i==6||t6>2)

                    for(j=max(2-t6,0);j<3;++j)

                        cnt+=dp[w-1][j];

                if(cnt>=x){putchar(i+48);break;}

                else x-=cnt;

            }if(i==6)++t6;else if(t6<3)t6&=0;--w;

        }putchar('\n');

    }

    return 0;

}

il int max(int a,int b){

    return a>b?a:b;

}

il void prepare(){

    dp[0][0]=1;

    for(int i(1);i<=20;++i)

        dp[i][1]=dp[i-1][0],dp[i][2]=dp[i-1][1],dp[i][3]=10*dp[i-1][3]+dp[i-1][2],

            dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])*9;

}

il void read(int &x){

    x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');

    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

}

巴特西

Apocalypse Someday

解

最新文章

热门文章