UVa 10706

　　题目大意：S_k表示从1到k的字符序列，如S₄为1234，现如今有如下的序列S₁S₂...S_k，形如1 12 123 1234这样的序列，给一个数n，让你去这个序列第n个位置上的数字。

　　可以构建出一个S_k序列的表格，然后用一个数组sum[i]记录该序列到i是有几位，这样就可以计算出n位于那个S_x序列中，求得在该序列中的位置，再查表即可。

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cctype>
 4 #include <climits>
 5 #define MAXN 100000
 6 
 7 long long sum[MAXN];
 8 char str[1000000];
 9 int k;
10 
11 void init()
12 {
13     k = sqrt(INT_MAX);
14     int p = 0;
15     for (int i = 1; i <= k; i++)
16     {
17         sprintf(&str[p], "%d", i);
18         while (isdigit(str[p]))  p++;
19     }
20     int tmp = 0;
21     sum[0] = 0;
22     for (int i = 1; i <= k; i++)
23     {
24         int cnt = 0, t = i;
25         while (t)
26         {
27             cnt++;
28             t /= 10;
29         }
30         tmp += cnt;
31         sum[i] = sum[i-1];
32         sum[i] += tmp;
33     }
34 }
35     
36 int main()
37 {
38 #ifdef LOCAL
39     freopen("in", "r", stdin);
40 #endif
41     init();
42     int T;
43     scanf("%d", &T);
44     while (T--)
45     {
46         int n;
47         scanf("%d", &n);
48         int low = 1, high = k;
49         while (low < high)
50         {
51             int mid = (low + high) / 2;
52             if (n <= sum[mid])  high = mid;
53             else  low = mid + 1;
54         }
55         int pos = n - sum[low-1];
56         printf("%c
", str[pos-1]);
57     }
58     return 0;
59 }

View Code