我的思路
一
因为每个序列的都是从1到N的,所以我们可以找到到n时,总的序列的长度是多少!
小序列标号 小序列的长度
1 1
2 2
. .
9 9 可以看出1-9,每次递增1
10 11
11 13
. .
99 ...
10-99递增2
由此可以找到当递增到31000多时,已经大于2^31了,我们把这31000多个数,打表。。
二
n一次减(从1)开始,当不够时,就可以找了。。。
700多MS,好挫啊
#include"stdio.h" #include"string.h" #include"stdlib.h" #include"math.h" #define N 32000 int mark[N]; int A[N]; char s[150001]; void init() { int i,t,j; memset(mark,0,sizeof(mark)); for(i=0;i<N;i=i*10+9) mark[i]=1; char ss[10]; s[0]=0; for(i=1;i<N;i++) { t=i; j=0; while(t) { ss[j++]=t%10+'0'; t/=10; } ss[j]=0; strrev(ss); strcat(s,ss); /*if(i==32000-1) printf("%d\n",strlen(s));*/ } int d=1; A[0]=0; for(i=1;i<N;i++) { A[i]=A[i-1]+d; if(mark[i]==1)d++; } } int main() { init(); int T; int n,i; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=1;i<N;i++) { if(A[i]<n) n-=A[i]; else break; } //printf("n==%d\n",n); printf("%c\n",s[n-1]); } return 0; }