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