PKU ACM-1019题 java Number Sequence

这道题只要找到序列之间的递推关系就可以了。题意就是说在给定的数字的字符串中的位置对应的数字是什么？

比如说给定数字式N那么求在序列的第N位上的数字是什么？

squ[i]=squ[i-1]+(数字i的位数如“10”是2位)；squ[i]表示“1234...i”中数字的个数

len[i]=len[i-1]+squ[i];len[i]表示“112123....1234..i”中数字的个数

然后先求出所有符合条件的len[i]进行判断。

import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		long[] len=new long[35000];
		long[] squ=new long[35000];
		Scanner cin=new Scanner(System.in);
		int caseNum=cin.nextInt();
		while(cin.hasNext()){
			int i=1;len[1]=1;squ[1]=1;
			long pos=cin.nextLong();
			while(len[i++]<pos){
				squ[i]=squ[i-1]+getDig(i);
				len[i]=len[i-1]+squ[i];
			}
			//System.out.println(squ[i-1]);
			if(len[i-1]==pos){
				System.out.println(i-1);
			}else{
				int j=1;
				while(squ[j++]<(pos-len[i-2])){
				}
				//System.out.println(squ[j]);
				if(squ[j-1]==(pos-len[i-2])){
					System.out.println((j-1));
				}else{
					long s=squ[j-1]-(pos-len[i-2]);
					while((s--)!=0){
						j/=10;
					}
					System.out.println(j);
				}
			}
		}
	}
	static long getDig(int i){
		long digit=1;
		while((i/10)!=0){
			i/=10;
			digit++;
		}
		return digit;
	}
}