题目背景
查找数字
题目描述
在下列的无穷数字序列1121231234123451234561234567123456781234567891234567 8910123456789101112345678910......中，查找第i个数字。
输入输出格式
输入格式：
第一行为正整数t(1≤t≤10)，表示测试数据组数。接下来t行，每行一个正整数i(1≤i≤2^31-1)。
输出格式：
对于每一个i，输出对应位置上的数字。
输入输出样例
输入样例#1： 复制
2
3
8
输出样例#1： 复制
2
2
主要思路：预处理 + lower_bound （STL大法好）
我们可以预处理一下一个数n的长度，预处理一下1n的长度，预处理一下1,12,13,...,1n的长度（听起来好麻烦的说）
预处理完毕以后，对于每一个查询n，我们可以用lower_bound找到第几位之前完整的1,12,13,...,1m，使得这个长度小于等于n且最大。然后再用lower_bound寻找最大的1k，使得这个长度小于等于n - length(1,12,13,...,1~m)且最大。这样就可以求出第n位所在的数中在第几位。所以我们只需要把第n位所在的数分解一下就好了。答案就是这个数的分解后第(n - length(1,12,13,...,1~m) - length(1~k))位
不太明白的话就手玩一下体会一下。
注意：
用可能减着减着，n会变成0，所以要加特判，当n减到0时，就把前面取到的数的最后一位输出即可
最近感冒QAQ有点晕
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define rep(i, x) for (int i = h[x]; i; i = e[i].nxt)
#define mn 100010
#define inf 2147483647
#define ll long long
#define ld long double
#define fi first
#define se second
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
//#define LOCAL
#define mod
#define Debug(...) fprintf(stderr, __VA_ARGS__)
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
//This is AC head above...
ll w[mn], a[mn], sum[mn], b[7];
int T, n;
inline void debug(int n = 20) {
go(i, 1, n, 1) printf("w[%2d] = %4d, a[%2d] = %4d, sum[%2d] = %4d
", i, w[i], i, a[i], i, sum[i]);
}
int main(){
go(i, 0, 9, 1) w[i] = 1;
go(i, 10, 99, 1) w[i] = 2;
go(i, 100, 999, 1) w[i] = 3;
go(i, 1000, 9999, 1) w[i] = 4;
go(i, 10000, 99999, 1) w[i] = 5;
a[1] = w[1];
go(i, 2, 99999, 1) a[i] = a[i - 1] + w[i];
sum[1] = a[1];
go(i, 2, 99999, 1) sum[i] = sum[i - 1] + a[i];
// 这鬼畜的预处理啊QAQ
//debug();
T = read();
while(T--){
n = read();
int now = lower_bound(sum + 1, sum + 100000, n) - sum - 1;
n -= sum[now];
if(n == 0) {
cout << now % 10 << "
";
continue;
}
now = lower_bound(a + 1, a + 100000, n) - a - 1;
n -= a[now];
if(n == 0) {
cout << now % 10 << "
";
continue;
}
int nn = now + 1;
fo(i, w[now + 1], 1, 1) {
b[i] = nn % 10;
nn /= 10;
}
cout << b[n] << "
";
}
#ifdef LOCAL
Debug("
My Time: %.3lfms
", (double)clock() / CLOCKS_PER_SEC);
#endif
return 0;
}