UVa 10706：Number Sequence

UVa 10706：Number Sequence2014-12-02链接：

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1647

原题：

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 80digits of the sequence are as follows:

11212312341234512345612345671234567812345678912345678910123456789101112345678910

Input

The first line of the input file contains a single integer t （1 <=t <=25）, 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.

样例输入：

样例输出：

题目大意：

一个数字序列由S1S2…Sk组成，其中Si也表示一个序列，为1，2，3....i. 输入一个数字i，然后输出这个序列中的第i位上的数字是多少。

分析与总结：

太挫了，只想到了模拟+找规律的方法。

首先可以发现一些规律：

每个位数的开始数字分别为1,10,100,1000,10000……可以把这些开始数字作为一个分界线。

用一个数组num来保存， num【i】表示数字位数为1,2…i这些位数的总和。

那么利用这个数组来求一个Si序列的总位数就很好办了，假设i=101，那么Si就是数字序列1,2…101，它的数字位数总和Si=（i-digit+1）*+num[digit-1], 其中digit表示i这个数的位数。

然后开一个数组S，S【k】用来保存S1S2…Sk这个序列的总位数。

预处理好这些信息之后,就可以开始查找和模拟了。

要查找第i位上的数字，那么首先要先查找到它是属于哪个Si，可以直接在S数组中二分查找下界，也就是查找到第一个>=i的。假设查找到的下标为k，如果S[k]刚好等于i，那么k这个数字刚好是Sk序列1,2,3……k的最后一个数，那么k%10就是答案了。

如果arr[k]>i，那么可以知道i是属于Si这个子序列之间的一个数。可以继续算得m=i-S【k-1】,那么答案那个位数的数字就在Si中的第m位。

接下来就是模拟，找出Si的第m位是多少。

可以根据num数组进一步缩小查找范围，在num数组中查找到>=m的第一个下标，假设该下标为p, 如果num【p】==m，说明那个位数正好处于分界线的最后一位，一定是9。

如果num【p】>m的话，那么可以算出那个位数处在上面表格中的哪个范围中，然后在那个范围中模拟算下去，一直到m位为止。求出第i位数字属于Si序列1,2,3……i中的哪个元素。具体还是看代码吧,文字真不太好表达。

代码：

/** UVa: 10706 - Number Sequence* Time: 0.008s* Author: D_Double**/#include<iostream>#include<cstdio>#include<algorithm>#define MAXN 31272using namespace std;long long S[MAXN];int scale[9]={0,1,10,100,1000,10000,100000,1000000,10000000};int num[9]={0,9,90,900,9000,90000,900000,9000000,90000000};inline int getDigit（int n）{int cnt=0;while（n>0）{++cnt;n /= 10;}return cnt;}inline void init（）{for（int i=2; i<9; ++i）{num[i] = num[i-1]+num[i]*i;}// 计算出S1,S2,S3..S5// 并且求出它们的和，及S[i]=S1+S2+..+SiS[0]=0;for（int i=1; i<MAXN; ++i）{int digit=getDigit（i）;S[i] = （i-scale[digit]+1）*digit+num[digit-1];S[i] += S[i-1];}}int main（）{init（）;int T, n;scanf（"%d",&T）;while（T--）{scanf（"%d",&n）;long long *p=lower_bound（S, S+MAXN, n）;if（*p==n） printf（"%d
",（p-S）%10）;else{int m=n-*（p-1）; bool ok=false;int j;for（j=0; j<9; ++j）{if（num[j]==m）{ok=true;break;}else if（num[j]>m）{break;}}if（ok）{printf（"9
"）;continue;}int left=m-num[j-1]; // 还要多少次int cnt=j;int k;for（k=scale[j]; cnt<left; cnt += j,++k）;;int time=cnt-left;while（time>0） {k/=10; time--;}printf（"%d
", k%10）;}}return 0;}

作者：csdn博客 shuangde800