首页 > 代码库 > SDUT OJ 1704 数字统计问题

SDUT OJ 1704 数字统计问题

SDUT OJ 1704 数字统计问题


博客原文地址:http://blog.csdn.net/xuechelingxiao/article/details/40930259


昨天晚上学弟问了OJ上这个题,群里说不清楚,就写个解题报告吧。


题目大意:

中文题目,就不翻译了-。-


解题思路:

不知道算不算一个典型的数位DP,反正有点那个意思,感觉确实也可以用记忆话搜索,两个差不多的意思。


我找了一下,这个问题好像是算法设计与实验题解上面的一道题,别的OJ上没有,所以就在自己OJ上做了。

大体的思路就是,对于一个数字,比如1342,想要求出每一个数字出自出现的次数,

对于一个n位的十进制数,从一个n位十进制数的由低到高的第i个数位上,总是连续出现10^i个0,然后是10^i个1……一直到10^i个9,9之后又是连续的10^i个0,这样循环出现。找到这个规律,就可以在常数时间内算出第i个数位上每个数字出现的次数。而在第i个数位上,最后再把前导0的数量去掉就是最后要的答案了。

这样最大的时间复杂度是数字位数,也就是log10(n)的复杂度,所以就不会超时了,最后跑了0ms。


吐槽一下宿舍的网,实在是太卡了,写个博客都这么费劲。。。。。真蛋疼。。。


具体的可以看代码,代码中会有部分解释:

#include <stdio.h>
#include <string.h>

int a[10], ans[10], len;
char s[10];

int main()
{
    a[0] = 1;
    for(int i = 1; i < 10; ++i) {
        a[i] = a[i-1]*10; ///a[i]记录 pow(10, i)
    }
    int n = 0;
    scanf("%s", s);///以字符串输入 便于统计长度
    len = strlen(s);
    for(int i = 0; i < len; ++i) {
        n = n*10+(s[i]-'0'); ///计算 n
    }
//    printf("%d\n", n);
    memset(ans, 0, sizeof(ans));
    for(int i = 0; i < len; ++i) {
        int num = s[i]-'0';
        int tmp = n/a[len-i-1];
        ans[num] += n+1-tmp*a[len-i-1];///从左到右 到第i+1位数字不变的前提下,第i+1位为num的数量
        tmp /= 10;
        int j = 0;
        while(j < num) {
            ans[j++] += (tmp+1)*a[len-i-1];
            ///记录当前位置 j 出现的次数
        }
        while(j < 10) {
            ans[j++] += tmp*a[len-i-1];
            ///记录当前位置 j 出现的次数
        }
        ans[0] -= a[len-i-1]; ///去掉前导零的数目
//        printf("%d\n", ans[0]);
    }
    for(int i = 0; i < 10; ++i) {
        printf("%d\n", ans[i]); ///打印结果
    }

    return 0;
}


SDUT OJ 1704 数字统计问题