题解 P1239 【计数器】

wjy666 · 2017-08-31 21:57:40 · 题解

楼下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<cstring>
#define N 10000
#define For(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int a[10];
void f(int y){ //计算一个数中每个数码出现次数
    while(y>0) a[y%10]++,y=y/10;
}
int main(){
    int n,x,b[10]={0},y; scanf("%d",&n); x=n/N;
    if (n<10000) For(i,1,n) f(i); //特判n<10000
    else {
        For(i,1,N-1) f(i); //算出前面的1-9999
        For(i,1,x-1){ //算中间一段，方法如上面所述
            memset(b,0,sizeof(b)); y=i;
            while(y>0) b[y%10]++,y=y/10;
            For(j,0,9) a[j]+=b[j]*N;
        }
        For(i,0,9) a[i]+=4000*(x-1); //后4位的贡献值一次性加上，不用一个一个加
        For(i,x*N,n) f(i); //算最后的一些数
    }
    For(i,0,9) printf("%d\n",a[i]); //输出
    return 0;
}