C++14(g++5.4) 解法, 执行用时: 8ms, 内存消耗: 400K, 提交时间: 2020-02-20 21:58:56

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long dp[21][4];
int x,m;
void init()
{
	dp[0][0]=1;
	for(int i=1;i<=20;i++)
	{
		for(int j=1;j<=3;j++)
		{
			dp[i][j]=dp[i][j]+dp[i-1][j-1];
			dp[i][0]=dp[i][0]+9*dp[i-1][j-1];
		}
		dp[i][3]=dp[i][3]+10*dp[i-1][3];
	}
}
int main()
{
	init();
	int T;
	cin>>T;
	while(T--)
	{
		scanf("%d",&x);
		for(m=3;dp[m][3]<x;m++);//第x个魔鬼数有m位
		for(int i=m,k=0;i;i--)//试填第i位，末尾已有k个6
		{
			for(int j=0;j<=9;j++)//从小到大枚举第i位填的数字j
			{
				long long cnt=dp[i-1][3];//求出后面的i-1位有多少种填法能让整个数是魔鬼数
				if(j==6||k==3)
					for(int l=max(3-k-(j==6),0);l<3;l++)
						cnt=cnt+dp[i-1][l];
				if(cnt<x)
					x=x-cnt;//如果cnt比n小，说明第n个魔鬼数的第i位应该比j更大
				else//否则第i位应该是j 
				{
					if(k<3)
					{
						if(j==6)
							k++;
						else
							k=0;	
					}
					printf("%d",j);
					break;
				}	 
			} 
		} 
		cout<<endl; 
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 412K, 提交时间: 2020-09-16 14:47:31

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[21][4];
int t,n,m;
void perwork(){
	f[0][0]=1;
	for(int i=0;i<20;i++){
		for(int j=0;j<3;j++){
			f[i+1][j+1]+=f[i][j];
			f[i+1][0]+=f[i][j]*9;
		}
		f[i+1][3]+=f[i][3]*10;
	}
}
int main(){
	perwork();
	cin>>t;
	while(t--){
		cin>>n;
		for(m=3;f[m][3]<n;m++);
		for(int i=m,k=0;i;i--){
			for(int j=0;j<=9;j++){
				ll cnt=f[i-1][3];
				if(j==6||k==3){
					for(int l=max(3-k-(j==6),0);l<3;l++){
						cnt+=f[i-1][l];
					}
				}
				if(cnt<n){
					n-=cnt;
				}else{
					if(k<3){
						if(j==6)  k++;
						else  k=0;
					}
					cout<<j;
					break;
				}
			}
		} 
		cout<<endl;
	}
	return 0;
}