定义一个数是合法的，当且仅当中间出现至少一个连续的大于三个的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();
}