题解 P1895 【数字序列】
Forever_Pursuit
2019-10-28 14:40:22
$\text{upd on 2020.2.28:}$ 增添了一些说明
题目描述
在下列的无穷数字序列$1121231234......$ 中，查找第 $n$ 个数字。
对于任意一个子数字序列 $1234...i$ ，我们可以先预处理出它的长度，记为$len_i$。
预处理部分代码（十分暴力，应该很好理解）：
```cpp
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$ 个数字，要先求出它在原序列哪个子序列中。
```cpp
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$ 个子序列的子序列。
于是我们继续枚举：
```cpp
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$ 取模。
然后把这个数求出来就行了。
```cpp
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;
}
```