这题只需要预处理两个数组就可以了，那就是一个保留从1到N，这个N个数字连在一起的长度，以及另外一个数组表示重复打印112123...123..N的这样一个打印到N的串的长度。接下来进行两次二分查找便可得到答案了。
代码如下：
#include#include #include #define MAXN 32000using namespace std;typedef long long int Int64;Int64 N, c[MAXN+5], s[MAXN+5];inline int Len(int x){ int ret = 0; while (x) { ++ret; x /= 10; } return ret;}void pre(){ for (int i = 1; i <= MAXN; ++i) { c[i] = c[i-1] + Len(i); } for (int i = 1; i <= MAXN; ++i) { s[i] = s[i-1] + c[i]; }}int bsearch(int l, int r, Int64 x[]){ int mid, ret; while (l <= r) { mid = (l + r) >> 1; if (x[mid] >= N) { r = mid - 1; ret = mid; } else { l = mid + 1; } } return ret;}int main(){ pre(); int pos, cnt, t, T; scanf("%d", &T); while (T--) { scanf("%I64d", &N); pos = bsearch(1, MAXN, s); N -= s[pos-1]; // 表示还剩余的位数 pos = bsearch(1, MAXN, c); if (c[pos] == N) { printf("%d\n", pos % 10); } else { cnt = 0; N = c[pos]-N; while (pos) { ++cnt; if (cnt == N+1) { printf("%d\n", pos % 10); } pos /= 10; } } } return 0; }