自动搬运

查看原文

来自洛谷，原作者为

	Falashiro 丝之歌什么时候出

搬运于2025-08-24 21:31:37，当前版本为作者最后更新于2019-10-28 14:40:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\text{upd on 2020.2.28:}$ 增添了一些说明

题目描述

在下列的无穷数字序列$1121231234......$ 中，查找第 $n$ 个数字。

对于任意一个子数字序列 $1234...i$ ，我们可以先预处理出它的长度，记为$len_i$。

预处理部分代码（十分暴力，应该很好理解）：

len[0]=0;
for(register int i=1;i<10;i++)
	len[i]=len[i-1]+1;
for(register int i=10;i<100;i++)
	len[i]=len[i-1]+2;
for(register int i=100;i<1000;i++)
	len[i]=len[i-1]+3;
for(register int i=1000;i<10000;i++)
	len[i]=len[i-1]+4;
for(register int i=10000;i<100000;i++)//预处理大一点
	len[i]=len[i-1]+5;

对于题目所求的序列的第 $n$ 个数字，要先求出它在原序列哪个子序列中。

scanf("%d",&n);
int s=0,k1=0,t=n;
while(++k1){
	s+=len[k1];
	if(s>=t)break;//保证s>=t,s-len[k1]<t
}
t-=(s-len[k1]);//s-len[k1]即为前(k1-1)个子序列的总长度

这样，我们就知道了答案就是第 $k_1$ 个子序列中的第 $t$ 个数。

显然对于任意一个 $i$ $(i∈N^+)$ ，第 $i$个子序列是第 $i+1$ 个子序列的子序列。

于是我们继续枚举：

int k2=0;
while(++k2)
	if(len[k2]>=t)break;//使得len[k2]>=t,len[k2-1]<t

即找到最小的 $k_2$ ，使第 $k_2$ 个子序列是至少有 $t$ 位的。

答案就变成了第 $k_2$ 个子序列中的倒数第 $(len_{k_2}-t+1)$ 个数，也就是 $k_2$ 这个数的倒数第 $(len_{k_2}-t+1)$ 位数。

如过要求一个数 $x$ 的倒数第 $y$ 位，就是求 $x/10^{y-1}$ 对 $10$ 取模。

所以 $k_2$ 的倒数第 $(len_{k_2}-t+1)$ 位就是 $k_2/10^{len_{k_2}-t}$ 对 $10$ 取模。

然后把这个数求出来就行了。

printf("%d\n",(int)(k2/pow(10,len[k2]-t))%10);

完整代码：

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define N 100001
int t,n,len[N];
int main(){
	for(rint i=1;i<10;i++)
		len[i]=len[i-1]+1;
	for(rint i=10;i<100;i++)
		len[i]=len[i-1]+2;
	for(rint i=100;i<1000;i++)
		len[i]=len[i-1]+3;
	for(rint i=1000;i<10000;i++)
		len[i]=len[i-1]+4;
	for(rint i=10000;i<100000;i++)
		len[i]=len[i-1]+5;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		int s=0,k1=0,k2=0;
		while(++k1){
			s+=len[k1];
			if(s>=n)break;
		}
		n-=(s-len[k1]);
		while(++k2)
			if(len[k2]>=n)break;
		printf("%d\n",(int)(k2/pow(10,len[k2]-n))%10);
	}
	return 0;
}