题目大意：有一个有0 ~ 9组成的序列，1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 。。。。就是第一位为1. 第二为为1 ，第三为为2， 然后10 的部分注意下， 为1 和0 两个， 100 就是1 ， 0和0 三位，以此类推， 要求给出tmp, 输出序列中的tmp位为什么数字。
解题思路：数据很大，肯定不能模拟，找规律。
这两个是为推出来的用来打表的公式:
1、sum[i] = sum[i - 1] * 2 - sum[i - 2] + w (w为当前i 的位数， sum[i]表示当前数字出现到i的时候占到序列的第几位）。
公式可以看成两部分， sum[i - 1] 和sum[i - 1] - sum[i - 2] + w.
sum[i - 1] 很明显是i - 1出现时所到达的位数， 那么开始生成i的时候，肯定是由sum[i - 1]这里开始的。
sum[i - 1] - sum[i - 2] + w就是从1 ~i所需要的位数， sum[i - 2] 为生成到i - 2所需要的个数，那么sum[i - 1] - sum[i - 2] 就为1 ~ i-1所需要的位数， 生成i - 1 和生成i只差了一个i,所以加上i的位数 就可以了。
2、num[i] = sum[i] - sum[i - 1],（num[i]为生成到i所需要的位数， 上面讲过了）
然后遍历一边sum数组， 找到第一个使得sum[i] >= tmp的i, 也就是说， tmp位的数是在生成1 ~i的过程中产生的数， 所以问题可以转换成找生成1 ~ i过程中的tmp - sum[i - 1]位。
接下来遍历一遍num数组，找到第一个i使得num[i] >= tmp的i, 也就是说， 处理过的tmp是在生成i的过程中产生的数，
输出tmp - num[i - 1]位与数i对应的位数值。
#include <stdio.h>
#include <stdlib.h>
const int N = 350000;
const int MAX = 2147483647;
const int w[] = {0, 10, 100, 1000, 10000, 100000};
int n = 2, num[N];
long long sum[N];
void init() {
sum[0] = num[0] = 0, sum[1] = num[1] = 1;
for (int cur = 1; sum[n - 1] < MAX; n++) {
if (n >= w[cur]) cur++;
sum[n] = sum[n - 1] * 2 - sum[n - 2] + cur;
num[n] = sum[n] - sum[n - 1];
}
}
int main () {
init();
int cas, tmp, cur;
char str[10];
scanf("%d", &cas);
while (cas--) {
scanf("%d", &tmp);
for (cur = 1; cur < n; cur++)
if(tmp <= sum[cur]) break;
tmp -= sum[cur - 1];
for (cur = 1; cur < n; cur++)
if (tmp <= num[cur]) break;
tmp -= num[cur - 1];
sprintf(str, "%d", cur);
printf("%c
", str[--tmp]);
}
return 0;
}