poj1019 大数据处理分块

Number Sequence

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 33215		Accepted: 9490

Description

A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2...Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another.
For example, the first 80 digits of the sequence are as follows:
11212312341234512345612345671234567812345678912345678910123456789101112345678910

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)

Output

There should be one output line per test case containing the digit located in the position i.

Sample Input

2
8
3

Sample Output

粗看想暴力过的，看到20几亿的数据不用想时间肯定超时。昨晚把边界数据大小数了下，本想很繁的题目，今晚真正上机写完估计不用5分钟，当然代码质量可能不是很高，可以更精简些。提交后RE了好几次，就很郁闷了。最后发现一个变量打错，丢死人

记录一下统计结果，当然如果有更好的写法这些数据可能用不上

1~9        共45位

10~99      共9000位               45+9000=9045

100~999    共1386450位            45+9000+1386450=1395495

1000~9999  共188019000位          45+9000+1386450+188019000=189414495

10000~9999 共23750235000位

第2147483647位于第31268个1...n中

本题用分块方法写的，也许是最笨的写法，有其他更好写法，欢迎指导

#include
   
    
#include
    
      using namespace std; long a[31270]={0},t,sum=0,i,j,k,len,h,g; long b[490000]={0}; long f(long n,long x){ len=0; for(g=n;g>=1;g--){ h=g; while(h){ b[len++]=h%10; h/=10; } } return b[len-x]; } int main(){ for(i=1;i<10;i++){ a[i]=a[i-1]+1; sum+=a[i]; } for(i=10;i<100;i++){ a[i]=a[i-1]+2; sum+=a[i]; } for(i=100;i<1000;i++){ a[i]=a[i-1]+3; sum+=a[i]; } for(i=1000;i<10000;i++){ a[i]=a[i-1]+4; sum+=a[i]; } for(i=10000;i<100000&&sum<=2147483647;i++){ a[i]=a[i-1]+5; sum+=a[i]; } cin>>t; if(t<1||t>10)return 0; while(t--){ cin>>i; if(i<1||i>2147483647)return 0; k=i; if(i>189414495){ k-=189414495; for(j=10000;;j++){ if(k>a[j]){ k-=a[j];continue; } else{ cout<
     
      1395495){ k-=1395495; for(j=1000;;j++){ if(k>a[j]){ k-=a[j];continue; } else{ cout<
      
       9045){ k-=9045; for(j=100;;j++){ if(k>a[j]){ k-=a[j];continue; } else{ cout<
       
        45){ k-=45; for(j=10;;j++){ if(k>a[j]){ k-=a[j];continue; } else{ cout<
        
         =1){ for(j=1;;j++){ if(k>a[j]){ k-=a[j];continue; } else{ cout<

poj1019 大数据处理 分块