题意分析

题目要求我们找到第$n$个野兽数字，即**至少包含三个连续的$6$**的正整数。例如，前几个野兽数字是：

• $666$（第$1$个）
• $1666$（第$2$个）
• $2666$（第$3$个）
• $\ldots$
• $6666$（第$6$个）
• $66666$（第$187$个）

给定$T$个查询，每个查询给出一个$n$，要求输出第$n$个野兽数字。

解题思路

由于$n$的范围可能很大（$1 \leq n \leq 5 \times 10^7$），直接枚举所有数字并检查是否包含$666$显然效率太低。因此，我们需要一种更高效的方法来生成野兽数字。

方法1：数位生成法

我们可以按数字的位数从小到大生成所有可能的野兽数字：

1. 3位数：只有$666$。
2. 4位数：形式为$\overline{X666}$或$\overline{666X}$，其中$X$是$1$到$9$的数字。
3. 5位数及以上：类似地，可以在不同位置插入$666$，并填充其他数字。

这种方法需要仔细处理重复和顺序问题，但可以高效生成所有野兽数字。

方法2：二分答案 + 数位DP

1. 二分答案：假设当前检查的数字是$mid$，我们需要计算$\leq mid$的野兽数字的个数$cnt$。如果$cnt \geq n$，则答案在左半区间；否则在右半区间。
2. 数位DP：用于计算$\leq mid$的野兽数字的个数。状态可以设计为：
   • 当前位数$pos$
   • 是否已经出现$666$（$has\_beast$）
   • 前几位是否是连续的$6$（$last\_six$）
   • 是否受$mid$的限制（$limit$）

这种方法适用于较大的$n$，但实现较为复杂。

方法3：预处理 + 直接查询

由于$n$的范围是$5 \times 10^7$，我们可以预处理前$5 \times 10^7$个野兽数字，然后直接回答查询。这种方法适用于多次查询，但预处理时间可能较长。

标程

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,x,f[25][4];
void cl()
{
	f[0][0]=1;
	for(int i=0;i<20;i++)
	{
		for(int j=0;j<=2;j++)
		{
			f[i+1][j+1]+=f[i][j];
			f[i+1][0]+=f[i][j]*9;
		}
		f[i+1][3]+=10*f[i][3];
	}
}
int main()
{
	scanf("%d",&t);
	cl();
	while(t--)
	{
		scanf("%d",&x);
		int m;
		for(m=3;f[m][3]<x;m++);
		for(int i=m,k=0;i>=1;i--)
			for(int j=0;j<=9;j++)
			{
				long long cnt=f[i-1][3];
				if(j==6||k==3)
					for(int l=max(0,3-k-(j==6));l<3;l++)
						cnt+=f[i-1][l];
				if(cnt<x)
				{
					x-=cnt;
					continue;
				}
				else
				{
					if(k<3&&j==6)k++;
					if(k<3&&j!=6)k=0;
					printf("%d",j);
					break;
				}
			}
		printf("\n");
	}
	return 0;
}