链接：
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
更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
There should be one output line per test case containing the digit located in the position i.
样例输入：
2
8
3
样例输出：
2
2
题目大意：
一个数字序列由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 31272
using 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+..+Si
S[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\n",(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\n");
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\n", k%10);
}
}
return 0;
}
作者：csdn博客 shuangde800
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， include
， uva
， integer
， sequence
The
sequence、oracle sequence、mysql sequence、boot sequence、create sequence，以便于您获取更多的相关知识。