洛谷P1895 数字序列 题解

题目链接：P1895 数字序列

题意：

$Q$ 组询问 $n$ 在下列的无穷数字序列的数码（ 显然是 $1 \sim 9$ ）

1121231234123451234561234567123456781234567891234567 8910123456789101112345678910…

输入格式：

第一行为正整数 $Q(1\le Q\le 10)$ ，表示测试数据组数。

接下来 $Q$ 行，每行一个正整数 $n~(1\le n\le 2^{31}-1)$ 。

输出格式:

对于每一个 $n$ ，输出对应位置上的数字。

我们可以把 12345 和 123456 这种子串记作 $f(5),f(6)$

并定义 $f(x) + f(x+1)$ 表示将 $f(x)$ 与 $f(x+1)$ 拼接起来，则原序列就是 $\sum_{x = 1}^{\infty} f(x)$

记 $\operatorname{size} \left(\sum_{i=1}^{n}f(i)\right)$ 为 $\sum_{i=1}^{n}f(i)$ 的长度。

注意到 $\operatorname{size}\left(\sum f\right)$ 的增长速度是极快的，而 $n \le 2^{31} -1$

因此存在阈值 $N$ 使得 $f(N)$ 后面的所有字符都没有意义。

打个表可以发现 $N = 31268$ ，且 $\operatorname{size}f(N) = 145234$ 。

因此对于每个询问，我们可以先预处理 $S_k = \operatorname{size} \left(\sum_{i=1}^{m}f(i)\right)$

然后二分出一个 $p$ 使得 $S_p \le n$ 。

由于 $\operatorname{size}f(N) = \mathcal{O}(10^5)$ ，因此我们可以直接暴力计算 $f(p+1)$

在计算的过程中判断一下超没超就好了。

时间复杂度 $\mathcal{O}(Q \times 10^5)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N 31270

int Q,x,l,tmp,a[N+15],pwd[15];
int solve(int x,int i)
{ return (x/pwd[i-1]) % 10; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    pwd[0] = 1;
    for(int i=1; i<=13; i++)
        pwd[i] = pwd[i-1] * 10;
    for(int i=1; i<=N; i++)
    {
        tmp += to_string(i).size();
        a[i] = a[i-1] + tmp;
    }
    for(cin >> Q; Q--; )
    {
        cin >> x; tmp = 0;
        int p = upper_bound(a+1, a+1+N, x) - a - 1;
        x -= a[p]; if(!x){ cout << solve(p,1) << '\n'; continue; }
        for(int i=1; i<=p+1; i++)
        {
            tmp += (l = to_string(i).size());
            if(tmp >= x)
            {
                tmp -= l; tmp = x - tmp;
                // cout << "l-tmp+1 = " << l - tmp + 1 << '\n';
                cout << solve(i, l - tmp + 1) << '\n'; break;
            }
        }
    }
    return 0;
}