Description
Sol
这题长得就比较像数位$DP$叭.
所以先用$DP$进行预处理,再基于拼凑思想,通过"试填法"求出最终的答案.
设$F[i][3]$表示由$i$位数字构成的魔鬼数有多少个,$F[i][j](0<=j<=2)$表示由$i$位数字组成的,开头有$j$个$6$的非魔鬼数有多少个.注意,在计算$F[i][j]$时允许前导$0$的存在
$F[i][0]=9*(F[i-1][0]+F[i-1][1]+F[i-1][2])$
$F[i][1]=F[i-1][0]$
$F[i][2]=F[i-1][1]$
$F[i][3]=F[i-1][2]+10*F[i-1][3]$
预处理完成之后,我们先通过$F[i][3]$确定第$X$小魔鬼数的位数,然后从左到右进行试填,试填的数从小到大枚举
Code
#include<iostream> #include<cstdio> #include<cmath> #define Rg register #define il inline #define db double #define ll long long #define go(i,a,b) for(Rg int i=a;i<=b;i++) #define yes(i,a,b) for(Rg int i=a;i>=b;i--) using namespace std; il int read() { int x=0,y=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=(x<<3)+(x<<1)+c-‘0‘;c=getchar();} return x*y; } int T,n,d,k; ll f[21][4]; il void init() { f[0][0]=1; go(i,1,20) { f[i][0]=9*(f[i-1][0]+f[i-1][1]+f[i-1][2]); f[i][1]=f[i-1][0]; f[i][2]=f[i-1][1]; f[i][3]=f[i-1][2]+10*f[i-1][3]; } } int main() { init();T=read(); while(T--) { n=read();d=3;k=0; while(f[d][3]<n)d++; yes(i,d,1) { go(j,0,9) { //求若第i位为j,那么剩下i-1位有多少种填法能使这个数成为魔鬼数 ll ct=f[i-1][3]; if(j==6 || k>=3) go(t,max(0,3-k-(j==6)),2)ct+=f[i-1][t]; if(ct<n)n-=ct;//应该填一个更大的数 else //就填j { if(j==6)k++;else if(k<3)k=0; printf("%d",j);break; } } } printf("\n"); } return 0; }