`
lovnet
  • 浏览: 6671427 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

NYOJ 413 && POJ 1019 Number Sequence(模拟)

 
阅读更多

题目链接:Click here~~

很早以前就看懂的一道题,当时不会做,今天在poj看到了, 有点思路,就写了。

题意:

有一个很长的串(称为大串),它由若干个小串相连,且小串i为它之前小串i-1加数字i组成,问此大串中第n位是哪个数字。

解题思路:

我们观察小串的规则可以看出,串i的长度等于串i-1的长度加上数字i的长度,而数字i的长度很容易求出来,所以我们可以由递推求出每个串的长度。

而根据每个串的长度,我们可以确定第i个串在大串中的位置,即前i串的长度和。

从而我们可以先通过找到小于n的且最大的串的位置,两个位置相减即可得到所求数字在小串中的位置th。

然后以同样的思想在小串的长度中找到小于th且最大的小串的长度,相减即可得到它在某一数字中的位置k,那个串的序数即为数字num。

然后求num的第k位即可。

#include <math.h>
#include <stdio.h>
#include <limits.h>
int dig[31269];
long long sum[31269];
void ac_table()
{
    for(int i=1;i<=31268;i++)
    {
        dig[i] = dig[i-1] + log10(i)+1;
        sum[i] = sum[i-1] + dig[i];
//        printf("%d----->%lld\n",i,dig[i]);
//        sum += dig[i];
//        if(sum > INT_MAX)                  //31268
//            break;
    }
}
int ac(int num,int k)
{
    int i=0,dd[7];
    while(num)
    {
        dd[i++] = num%10;
        num /= 10;
    }
    return dd[i-k];
}
int main()
{
    int z,n,k,th,num;
    ac_table();
    scanf("%d",&z);
    while(z--)
    {
        scanf("%d",&n);
        for(int i=0;;i++)
        {
            if(sum[i+1] >= n)
            {
                th = n - sum[i];
//                printf("th-->%d\n",th);
                break;
            }
        }
        for(int i=0;;i++)
        {
            if(dig[i+1] >= th)
            {
                k = th - dig[i];
                num = i+1;
//                printf("num-->%d\n",num);
                break;
            }
        }
        printf("%d\n",ac(num,k));
    }
	return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics