解法:数位dp
状态表示:$f_{i,j}$表示由$i$个数组成的数,左边有连续$j(0\le j\le 3)$个$6$
边界:$f_{0,0}=1$
转移方程:
$$
f_{i,0}=9\times(\sum_{j=0}^2f_{i-1,j})(可以在至多连续2个6前填0,1,…,5,7,…,9)\\
f_{i,1}=f_{i-1,0}(从连续0个6前补一个6)\\
f_{i,2}=f_{i-1,1}(从连续1个6前补一个6)\\
f_{i,3}=10\times f_{i-1,3}+f_{i-1,2}(从连续3个6转移或从连续2个6前补一个6)
$$
解法:枚举可以满足的数的个数,确定每一位的数
code:
#include<bits/stdc++.h>
using namespace std;
int t,x,f[21][4];
int main(){
//dp
f[0][0]=1;
for(int i=1;i<=20;i++){
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];
}
cin>>t;
while(t--){
cin>>x;
//确定位数
int n=1;
while(f[n][3]<x) n++;
int cnt=0;//连续6的个数
for(int i=1;i<=n;i++){
for(int j=0;j<=9;j++){
int c6=3;//至少要填几个连续的6
if(cnt==3) c6=0;
else if(j==6) c6=2-cnt;//如果这一位填6,就和前cnt个拼起来
int sum=0;
for(int k=c6;k<=3;k++) sum+=f[n-i][k];
if(sum>=x){
//成功就输出这一位的数
cout<<j;
if(cnt<3){
if(j==6) cnt++;
else cnt=0;
}
break;
}else x-=sum;//如果小了,就继续枚举
}
}
cout<<endl;
}
return 0;
}