【解题报告】 启示录

题目描述

探险队员终于进入了金字塔。通过对古文字的解读， 他们发现，和《圣经》的作者想的一样，古代人认为 666 是属于魔鬼的数。不但如此，只要某数字的十进制表示中 有三个连续的 6，古代人也认为这个是魔鬼的数，比如 666, 1 666, 2 666, 3 666, 6 663, 16 666, 6 660 666 等等，统统是魔 鬼的数。 古代典籍经常用“第 X 大的魔鬼的数”来指代这些数。 这给研究人员带来了极大的不便。为了帮助他们，你需要写一个程序来求出这些魔鬼的数字。

输入格式

输入文件包含多组测试数据。第一行有一个整数 T 表示测试数据的组数。 每组测试数据包含一个整数 X，表示需要求第 X 大的魔鬼的数。

输出格式

对于每组测试数据，在一行内输出结果。

输入输出样例

输入 #1

1
2
3
4
3
2
3
187

输出 #1

1
2
3
1666
2666
66666

说明/提示

对于 20% 的数据，保证 X≤10e6。 对于 100% 的数据，保证 T≤1 000，X≤50 000 000。

解题思路

这是一个标准的数位Dp，我们只需要简单地找出他的动态转移方程，然后用试数法（我更乐意叫此为“夹逼法”），就可以得出答案了

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long long f[21][4];
int t,n,m;
void init()
{
	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()
{
	init();
	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++)
			{
				long long 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;
}