[POJ 1019]数字处理

【题目大意】有这样一个序列,1,112,112123,1121231234,112123123412345…,求它的第X位是多少。

【算法分析】

构造,分步骤来求,逐步逼近答案。

先对序列进行分组,即按1,12,123,1234,12345这样分组,利用递推求出前I组数的位数,即Sum[I]:=Sum[I-1]+F[I],F[I]:=F[I-1]+Trunc(ln(I)/ln(10))+1。

这样,我们可以很容易确定第X位的所在组(当组大于40000时,位数已经超过Maxlongint)

然后在用While循环求出第X位是这个组中的第几个数,再求出是这个数的第几位即可。

【其它】复杂度约为O(sqrt(n))

6429639 edward2 1019 Accepted 884K 16MS G++ 1094B 2010-02-09 20:10:37

【CODE】

#include

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注