首页 > 代码库 > poj 1019 分块

poj 1019 分块

2024-07-09 00:59:13   220人阅读

题目来源：

http://poj.org/problem?id=1019

 

题意： 有一串数字串，其规律为

1 12 123 1234 12345 123456 1234567 12345678 123456789 12345678910 1234567891011 123456789101112······k

输入位置n，计算这一串数字第n位是什么数字，注意是数字，不是数！例如12345678910的第10位是1，而不是10，第11位是0，也不是10。总之多位的数在序列中要被拆分为几位数字，一个数字对应一位。

 

分析：

分块 

序列【1 2 .. i 】 为第i 组

const int Max_N = 40000 ;LL a[Max_N] , sum[Max_N] ; //a[i] 为第i组的长度， sum[i] 为前i(包括i)组的总长度int main(){    int i,j ;    sum[0] = a[0] = 0 ;    for(i = 1 ; i < Max_N ; i++){        a[i] = a[i -1] + (int)log10((double) i) + 1 ;        sum[i] = sum[i - 1] + a[i] ;    }    int t , n;    scanf("%d" , &t) ;    while(t--){        scanf("%d" , &n) ;        i = 0 ;        while(sum[i] < n) i++ ;  // 确定n在第i组        int pos = n  - sum[i - 1] ;  // 确定n在第i组的第pos个位置        int len = 0 , i = 0;        while(len < pos){            i++;            len += (int)log10((double) i ) + 1 ;        }        printf("%d\n" , i / (int)pow(10.0 , len - pos) % 10) ;    }    return 0 ;}

 


联系
我们