首页 > 代码库 > poj1019 大数据处理 分块

poj1019 大数据处理 分块

2024-07-02 08:32:01   224人阅读

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

2
粗看想暴力过的，看到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<iostream>
#include<cmath>
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<<f(j,k)<<endl;
		  		break;
		  	}
		  }	
		}
		else if(i>1395495){
			k-=1395495;
			for(j=1000;;j++){
				if(k>a[j]){
					k-=a[j];continue;
				}
				else{
					cout<<f(j,k)<<endl;
		  		    break;
				}
			}
		}
		else if(i>9045){
			k-=9045;
			for(j=100;;j++){
				if(k>a[j]){
					k-=a[j];continue;
				}
				else{
					cout<<f(j,k)<<endl;
		  		    break;
				}
			}
		}
		else if(i>45){
			k-=45;
			for(j=10;;j++){
			  if(k>a[j]){
					k-=a[j];continue;
			  }
			  else{
					cout<<f(j,k)<<endl;
		  		    break;
			  }	
			}
		}
		else if(i>=1){
			for(j=1;;j++){
			  if(k>a[j]){
					k-=a[j];continue;
			  }
			  else{
					cout<<f(j,k)<<endl;
		  		    break;
			  }		
			}
		}
	}
  return 0;
}






























        

            
                
                  
                
                

                    联系

                    我们