uva 10706 - Number Sequence

点击打开链接uva 10706

题目意思：    有一个数组 s[1] = 1 , s[2] = 1 2 , .......s[k] = 1....k，要求给定一个n表示数组的第几位，要求这个第几位是什么数。例如 n为1 时候是1 n为 2 时候是1 ，n 为3 时候为2

解题思路：    1:思路：预处理打表+查找
                     2:题目给的数据可以发现一些规律
                        s[1]：1                                   总位数1
                        s[2]：1 2                                总位数1+2 = 3
                        s[3]：1 2 3                             总位数1+2 +3 = 6
                        .
                        .
                        .
                        s[9]：1 2 3 4 5 6 7 8 9          总位数1+2 +3+...+9 = 45
                        s[10]:  1 2 3 4 5 6 7 8 9 10    总位数45+1+2 +3+...+9 +1+0 = 56
                        s[K]：1 2 3 4 . . . . . . k           总位数 num[k-1]+1+2+......
                                               用num[k]保存当值为k时候总的位数.
                      所以我们要是能够预先把所有的数据全部求出弄成一张表，然后输入的时候直接查找位于那个位置，然后在去查找这个位置 ,由于上面的递增趋势，我么可以推断当k到100000时候就会超过int，所以开个这么大的数组就可以了。
                     3:打表过程:我么采用枚举当前值的位数，例如位数为1，那么就有1-9共9位数，如果位数为2就有10-99公共90个.......假设当前的数值为n，那么根据上面的规律求出num[n]，一次这样求出所以数据
                     4:查找，O(n)的时间复杂度，只要找到num[i-1] < n, num[i]>=n , 那么我们可以知道这个数存在s[n]中,把n减去num[i-1]，可以知道要求的数在s[n]中第几位，然后再去一一判断。注意这里n可能为1234等多位数，那么要把他拆开，这时候是先拆前面即最大位。
                     5注意事项:由于这一题的n最大为2147483647，那么我们开得num数组要为long long，中间的一些处理也要为long long不然会有精度缺失

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define MAXN 100000

int  t , n;
long long  num[MAXN];//保存某一个值的总数

//打表初始化
void init(){
    long long i , j , k , tmp;//long long注意
    memset(num , 0 , sizeof(num));//初始化
    for(i = 1 ; i <= 5 ; i++){//枚举位数，最大到5位即可
        for(j = pow(10,i-1) ; j < pow(10,i) ; j++){
            num[j] = num[j-1] ; tmp = (j-pow(10,i-1)+1)*i;
            for(k = 1 ; k < i ; k++)
                tmp +=(pow(10,k)-pow(10,k-1))*k;
            num[j] += tmp;
        }
    }
}

void solve(){
    int i , j , k , pos , ans;
    //找到pos位置
    for(i = 1 ; i < MAXN ; i++){
        if(n > num[i-1] && n <= num[i]){
            pos = i ; break;
        }
    }
    //查找
    int cnt = n-num[pos-1] ; int sum = 0;
    int len , tmp , tmp_j;
    for(j = 1 ; j <= pos ; j++){
        tmp_j = j;
        for(i = tmp_j , len = 0 ; i != 0 ; i/=10) len++;
        for(k = len-1; k >= 0 ;k--){
            ans = tmp_j/pow(10,k) ; sum++;
            if(sum == cnt){            
                printf("%d\n" , ans);
                return;
            }
            tmp = pow(10,k) ; tmp_j %= tmp;
        }
    } 
}

int main(){
    //freopen("input.txt" , "r" , stdin);
    init() ; scanf("%d" , &t); 
    while(t--){
        scanf("%d" , &n) ; solve();
    }
    return 0;
}