LuoGu-P1239计数器-强大的贡献

P1239 计数器

题意：就是求从1到n间，1～9一共出现的次数

这道题直接暴力是不科学的，因为N有 1e9；

然后我就看到了一个很好的从贡献思考的方法；

——>转自洛谷学神的方法：

楼下dalao都是数学方法和数位dp，看的本蒟蒻心慌慌

如果对高级方法难以理解的话，这里提供一种简单方法，虽然效率比dalao们差很多，但是对于本题已经够了

对于每一个数x，可以分为x/10000和x%10000两个部分(也就是前几位和后4位)

那么对于中间很大一段数字，同样的前几位会重复出现一万次，后4位就是0000-9999

所以对于中间这一段，可以枚举前几位，贡献值乘以1万，然后每枚举一个，0-9的出现次数加上4000就是后4位的贡献值

(0000-9999总共4万个数码，每个数码出现次数都相等)

然后前面的1-9999和最后一截前几位没出现1万次的数暴力算就行了

这份代码绝对容易理解，而且对于这题也是0ms（自己理解了比较久。。。

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <string>

#include <cstring>

const int N = ;

using namespace std;

int n,a[],b[];

void f(int x)                //计算一个数中每个数码出现次数

{

    while( x>) a[x%]++,x/=;

}

int main(){

    scanf("%d",&n);int x = n/N;

    if(n<)                //计算一个数中每个数码出现次数

    {

        for(int i=; i<=n; i++)

            f(i);

    }

    else

    {

        for(int i=; i<N; i++)f(i);    //算出前面的1-9999

        for(int i=; i<x; i++)        //算中间一段，方法如上面所述

        {

            memset(b,,sizeof(b));

            int y = i;

            while(y>) b[y%]++,y/=;

            for(int i=; i<; i++)a[i]+=b[i]*N;

        }

        for(int i=; i<; i++)a[i]+=*(x-);//后4位的贡献值一次性加上，不用一个一个加

        for(int i=x*N; i<=n; i++)f(i);            //算最后的一些数

    }

    for(int i=;i<;i++)

        printf("%d\n",a[i]);                    //输出

    return ;

}

巴特西

LuoGu-P1239计数器-强大的贡献

P1239 计数器

最新文章

热门文章