ACM 1410 . 求算法
http://acm.zju.edu.cn/show_problem.php?pid=1410
---------------------------------------------
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "math.h"

int main()
{
char arry[200000];
char temp[100];
int step[50000];
int n,i;
int cur,p;
unsigned int len,sum=0;


arry[0]=0; i=1;len=0;
while(sum<=2147483647)
{
sprintf(temp,"%d",i);
len=len+strlen(temp);
step[i]=len;
sum+=len;
strcat(arry,temp);
i++;
}

scanf("%d",&n);
while(n--)
{
scanf("%d",&i);

cur=0;
p=i;
while(p>0)
{
cur++;
p=p-step[cur];
}

p=p+step[cur]-1;

printf("%c",arry[p]);

}
return 0;
}

[解决办法]
忘记改了，应是：
在1，2，3，4，5，6，7，8，9，10，11，12中数字1出现的次数是1+1+2+1=5次。（分别在1，10，11，12处出现）
[解决办法]
我上面的方法其实还可以优化。

“k=1,2,...依次计算T(k)（计算方法后面再讲），sum+=T(k)。若发现在某个k时,sum >i，那么，就说明第i个出现在Sk中，”

由于T(k)是递增的，因此，上面的过程可以用折半查找来实现。这样的话，复杂度就很低了。

另：计算Y(k,i)的方法可以有计算y(k,1)的方法类比得到。
[解决办法]
设:
f1(k)=len(1 & 2 & .... & k);
f2(k)=len(f1(1)& f1(2) & .... & f1(k)) ;
那么：
f1(9)=9;
f1(99)=f1(1)+90*2;
f1(999)=f1(2)+900*3;
f1(9999)=f1(3)+9000*4;
f2(9)=45;
f2(99)=f2(9)*90+(1+2+3+....90)*2;
f2(999)=f2(99)*900+(1+2+3+....900)*3;
f2(9999)=f2(999)*9000+(1+2+3+....9000)*4;

对于范围[1,9],[10,99],[100,999],[1000,9999],[10000,99999]
f1,f2可以表示为函数，比如：
f1(i)=f1(9)+(i-9)*2 10<=i<=99;
f2(i)=f2(9)*i+(1+2...+(i-9))*2 10<=i<=99;

那么对于要求解的字符C;
由f2可以计算出该字符所在的f(k)以及其索引；
由f1可以计算出该字符所在的k以及其索引；