题解 P1895 【数字序列】

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;
}