一、题目大意

有这样一个序列包含S1，S2，S3...SK,每一个Si包括整数1到 i。求在这个序列中给定的整数n为下标的数。

例如，前80位为11212312341234512345612345671234567812345678912345678910123456789101112345678910，第8位为2.

二、题解

动手做这道题之前要了解所求的是第n位而不是某一个Si中的第几个数，一位数占一位，两位数占两位，三位占三位...由于每一组都比前一组多一个数，如果这个数是一位数，则该组数的位数比前一组多1，如果这个数是两位数，则比前一组多2，三位数则多3.这个可以用公式a[i] = a[i-1] +（int）log10((double)i) + 1;表示。我们可以用打表的方法，在求结果之前先打表，用a[i]表示第i组所含的位数，s[i]表示前i组所含的位数。对于每一个给定的位数，先求出它处在哪一个组，然后再求位数。参考POJ
1019 Number Sequence C++版

三、java代码

import java.util.*;   

public class Main {

	 static long a[]=new long[31270];//记录每一组的长度

	 static long s[]=new long[31270];//记录总长度

	/* 打表 */

	static void reset(){

	    int i;

	    a[1] = 1;

	    s[1] = 1;

	    for(i = 2; i < 31270; i++){

	        /* 每一组数字都比上一组长 (int)log10((double)i) + 1 */

	        a[i] = a[i-1] + (int)Math.log10((double)i) + 1;

	        s[i] = s[i-1] + a[i];

	    }

	}

	static int work(int n){ /* 计算 */

	    int i = 1;

	    int length = 0;

	    /* 找到 n 所在的组 */

	    while (s[i] < n) i++;

	    /* n 在该组的下标 */

	    long pos = n - s[i-1];

	    /* length: n指向的数字的最后一位的下标 */

	    //找到i

	    for (i = 1; length < pos; i++){

	        length += (int)Math.log10((double)i) + 1;

	    }

	    //i比所求的i多1

	    /* 除以10^(length - pos)去掉所求位后面的数字然后取余 */

	    /* i: n指向的数字 + 1 */

	    //

	    return ((i-1) / (int)Math.pow((double)10, length - pos)) % 10;

	}

    public static void main(String[] args) {

        Scanner sc= new Scanner(System.in);

        int t;

	    int n;

	    reset();

	    t=sc.nextInt();

	    while(t--!=0)

	    {

	        n=sc.nextInt();

	        System.out.println(work(n));

	    }

    }

}