POJ3208 Apocalypse Someday

题意

Language:Default Apocalypse Someday Time Limit: 1000MS Memory Limit: 131072K Total Submissions: 2499 Accepted: 1288 Description The number 666 is considered to be the occult “number of the beast” and is a well used number in all major apocalypse themed blockbuster movies. However the number 666 can’t always be used in the script so numbers such as 1666 are used instead. Let us call the numbers containing at least three contiguous sixes beastly numbers. The first few beastly numbers are 666, 1666, 2666, 3666, 4666, 5666… Given a 1-based index n, your program should return the nth beastly number. Input The first line contains the number of test cases T (T ≤ 1,000). Each of the following T lines contains an integer n (1 ≤ n ≤ 50,000,000) as a test case. Output For each test case, your program should output the nth beastly number. Sample Input 3 2 3 187 Sample Output 1666 2666 66666 Source POJ Monthly--2007.03.04, Ikki, adapted from TCHS SRM 2 ApocalypseSomeday

定义十进制下有3个连续的6的数为魔鬼数。有T个询问，求第k小的魔鬼数。

T<=1000,k<=5e7

分析

参照xyc1719的题解。

由于K有5e7那么大，哪怕线性dp，常数稍大就会有TLE的风险。如果内存小于128MB又会有MLE的问题显然，预处理出第k大的魔鬼数是不可靠的。

由于T较小，我们转而考虑能否像计数dp一样将先大致预处理出辅助数组，再进行“拼凑”。回答是可行的。但dp数组的定义是与数字的位数有关。

定义\(f[i,k]\)表示\(i\)位数，开头有\(k\)个连续的6的数的数目。注意允许出现前导0

状态转移方程：

\[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]+f[i−1,3]∗10
\]

每次在询问时，利用辅助数组进行转移。

注意设计状态转移方程时，注意不重复不遗漏

时间复杂度\(O(\log ans)\)

代码

#include<iostream>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;

ll f[21][4];
void prework(){
	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 n,m;
int main(){
	prework();
	for(int t=read<int>();t--;){
		read(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=std::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;
					}
					printf("%d",j);
					break;
				}
			}
		}
		puts("");
	}
	return 0;
}