find the nth digit

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768
K (Java/Others)

Total Submission(s): 11311 Accepted Submission(s): 3378

-> Link <-

这种题应该是数位dp吧，之前在cf上第一次碰见这种题，此后不断碰到类似变形的，不过poj上那道Number sequense还是没有A出来，这道题和cf上的那道很相似，用的就是类似的思路，不是很难；

思路：既然是1121231234.....9 123..91 123...912 123...91234...，我们观察数字规律，第1位是1，第3位是2，第10位是4，出现第1个9的时候是第45位，也就是说前45位位数n=(1+i)*i/2，类似于前n项和；而45位以后，每出现的一个字串的长度从10开始递增，最低位从1开始到9然后又从1开始到9，直到位数凑够n;

这样说可能有点不明白，还是用代码解释吧：

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int t,n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        int i=1;

        while(n>i)

        {

            n-=i;//反过来就是相当于前i项和；

            i++;

        }

        while(n>9) n-=9;//当其位数大于45时，就是上面所说的从1开始排到9又从1开始排到9.......所以。。

        printf("%d\n",n);

    }

    return 0;

}//自己在稿子上模拟一下很好理解的；

要不是在cf上看到那种题这道题还不造要做多久，不得不又感慨一下CF上的题真的很启发思维啊，一道题发散性思维就可以解决很多问题，收获很大，做这道题估计不超过半小时，稍微推一下直接A了，真的好开心！！

巴特西

HDU-1597find the nth digit，超短代码一遍过，啦啦啦啦~~

find the nth digit

最新文章

热门文章