🧠 题解思路

这道题目看似简单，其实考察的是：

如何在一个动态构造的无限数列中定位一个数字

如何高效处理范围非常大的 $i$（上限 $2 \times 10^9$）

📈 序列构造逻辑

记：

第 $k$ 段子串为：$S_k = 123\ldots k$（长度不等于 $k$，因为数字有多位）

整体数列：$S = S_1 + S_2 + S_3 + \ldots + S_k$

所以我们要找的是：第 $i$ 个字符属于哪个 $S_k$，再定位它在 $S_k$ 内是哪一个数的哪一位。

✅ 步骤详解

第一步：找出目标字符位于哪个 $S_k$ 中 我们需要累加每个 $S_k$ 的长度直到超过第 $i$ 位。

关键是：$S_k$ 的长度不是 $k$，而是长度为 $1$ 到 $k$ 所有整数拼接起来的长度。

子串 $S_k$ 的长度怎么求？ 我们从 $1$ 累加到 $k$，每个数 $n$ 的位数是 $\text{len}(n)$，所以：

len ( 𝑆 𝑘 )

∑ 𝑛

1 𝑘 digits ( 𝑛 ) len(S k ​ )= n=1 ∑ k ​ digits(n) 例如：

$S_3 = 1 + 2 + 3$ → 字符串为 123，长度 3

$S_10 = 12345678910` → 长度 11

因此，我们可以从 $k=1$ 开始，不断累加 $S_k$ 的长度，直到超过 $i$ 为止。

这部分时间复杂度为 $O(\sqrt{i})$ 左右。

第二步：确定位置 设目标落在 $S_k$ 中：

我们再遍历 $1 \sim k$，将 $1 \sim k$ 的数字拼接起来，直到达到目标位置。

将拼接好的字符串取出第 $i$ 位即可。

代码实现

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<set>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<string>
 
using namespace std;
 
#define N 31280
#define s 31268
 
int go[N];
int num[N];
int sum[N];
int getnum(int k)
{
	int j=10;
	int ans=1;
	while ( k/j)
	{
		j*=10;
		ans++;
	}
	return ans;
}
 
int main()
{
	int i,j,k;
	go[0]=0;
	for (i=1;i<N;i++)
	{
		go[i]=getnum(i);
	}
	num[0]=0;
	for (i=1;i<N;i++)
	{
		num[i]=num[i-1]+go[i];
	}
	sum[0]=0;
	for (i=1;i<N;i++)
	{
		sum[i]=sum[i-1]+num[i];
	}
 
	int n;
	int cas;
	cin>>cas;
	while (cas--)
	{
		cin>>n;
		for (i=s-1;i>=0;i--)
		{
			if ( n>sum[i])
			{
				n-=sum[i];
				break;
			}
		}
		//cout<<n<<' ';
		
		for (i=N-1;i>=0;i--)
		{
			if (n>num[i])
			{
				n-=num[i];
				break;
			}
		}
		//cout<<n<<' ';
		i++;
		k=1;
		//cout<<i<<' ';
		//cout<<go[i]<<' ';
		n=go[i]-n+1;
		while (--n)
		{
			i/=10;
		}
		cout<<i%10<<endl;
	}
}