洛谷 P1554(梦中的统计)题解

Bessie 处于半梦半醒的状态。过了一会儿,她意识到她在数数,不能入睡。Bessie 的大脑反应灵敏,仿佛真实地看到了她数过的一个又一个数。她开始注意每一个数码(0..9):每一个数码在计数的过程中出现过多少次?

给出两个整数 M 和 N(1 ≤ M ≤ N ≤ 2,000,000,000 以及 N-M ≤ 500,000),求每一个数码出现了多少次。

例如考虑序列 129–137:129,130,131,132,133,134,135,136,137。统计后发现:

0 出现了 1 次,1 出现了 10 次,2 出现了 2 次,3 出现了 9 次,4 出现了 1 次,5 出现了 1 次,6 出现了 1 次,7 出现了 1 次,8 出现了 0 次,9 出现了 1 次。

输入格式

第 1 行: 两个用空格分开的整数 M 和 N。

输出格式

第 1 行: 十个用空格分开的整数,分别表示数码(0..9)在序列中出现的次数。

输入输出样例

输入 #1

129 137

输出 #1

1 10 2 9 1 1 1 1 0 1

思路

逐个数进行统计。其实可以对 10 取模,提取最后一位数出来,再对整个数除以 10(向下取整)形成新的数,如此重复(这种思路的时间复杂度小于下面的做法)。这样可以得到各个数码,从而进行统计。 但最近一位有位神犇向本蒟蒻介绍了字符串骚操作必备之 sscanfsprintfstrcat,决定尝试 sprintf,这玩意发送格式化输出到指定的字符串。

char tmp[20];
for (int i = a; i <= b; i++) sprintf(tmp,"%d",i);

得到的字符减去 '0',就是数码了,多快好省。

AC 代码

更新:遍历字符串判断条件应该用 str[k] 节省时间。例如这里 tmp[j] 优于 j < strlen(tmp)

如下:

#include <stdio.h>
#include <string.h>
int n[10],a,b;
char tmp[20];
int main()
{
    for (int i = 0; i < 10; i++)
    {
        n[i]=0;
    }
    
    scanf("%d %d",&a,&b);
    for (int i = a; i <= b; i++)
    {
        sprintf(tmp,"%d",i);
        for (int j = 0; tmp[j]; j++)
        {
             int num=tmp[j]-'0';
             n[num]++;
        }
        
    }
    for (int i = 0; i < 10; i++) printf("%d ",n[i]);
    return 0;
}