这题目关键是打表，haha[k]数组表示的是S1S2..Sk该串结尾所在的位置。然后用n去找n所在的k值,此时haha[k-1]<n<=haha[k]。然后再算出从haha[k]位置到n一共有多少位，再查出来就行了。
本来我要用打表+二分的想法，不过后来二分写的不太好一看可以直接遍历就遍历，limit=3万多，直接遍历也行！有时间把这个二分好好的重写一下。
一点没看题解，做出来挺开心的！
1-9 的长度 = 9
1-99 的长度 = 189
1-999 的长度 = 2889
1-9999的长度 = 38889
31268是事先计算好的，haha[31268]时候正好大于临界值。
#include <stdio.h>
#define limit 31268
long long haha[];
void init(){
int cnt=,i;
int t;
haha[]=;
for(i=;i<=;++i){
haha[i]=haha[i-];
if(cnt>=){
haha[i]+=(cnt-+)*+;
}
else if(cnt>=){
haha[i]+=(cnt-+)*+;
}else if(cnt>=){
haha[i]+=(cnt-+)*+;
}else if(cnt>=){
haha[i]+=(cnt-+)*+;
}else if(cnt>){
haha[i]+=*cnt;
}
cnt++;
if(haha[i]>){
break;
}
}
return ;
}
int main(){
int t,ii,i,l,r,mid;
int n;
int pos;
int cnt;
int tmp;
int res;
init();
while(~scanf("%d",&t)){
while(t--){
scanf("%d",&n);
/*
l=0;
r=limit;
mid=(r+l)/2;
while(haha[r]>=n&&n>=haha[l]){
printf("l=%d,r=%d,haha[l]=%lld,haha[r]=%lld\n",l,r,haha[l],haha[r]);
if(n<haha[mid]){
r=mid;
}else if(n>haha[mid])
l=mid;
else break;
mid=(r+l)/2;
}
pos=mid;
*/
for(i=;i<=limit;++i){
if(haha[i]>=n)
break;
}
pos=i;
cnt=;
res=-;
// printf("n=%d,pos=%d,haha[pos]=%lld\n",n,pos,haha[pos]);
if(n-(int)haha[pos]<){
n=(int)haha[pos]-n;
n++;
for(i=pos;i>=;--i){
int ii=i;
while(ii>){
tmp=ii%;
ii=ii/;
cnt++;
if(cnt==n){
res=tmp;
break;
}
}
if(res!=-) break;
}
printf("%d\n",res);
}else if(n-(int)haha[pos]==){
printf("%d\n",pos%);
}
}
}
return ;
}