P2602 [ZJOI2010]数字计数

偷得题面

设f[i]代表第i位上不算前导零每个数出现多少次

比如54321

首先是5,,5在万位上,那么个十百千位每个数都会出现至少5*f[bit]次,然后万位上,5以下的数都会出现,然后以此类推

最后加完所有位之后,在处理4321这样的跑不满的零位就好了qwq

代码

#include <bits/stdc++.h>
#define int long long
using namespace std ;
int a , b ;
int ten[15] , f[15] ;
int cnta[15] , cntb[15] , num[10] ;
void work(int x ,int cnt[])  {
    for(int i = 0 ; i < 10 ; i ++) num[i] = 0 ;
    int len = 0 ;
    while(x) {//拆数
        num[++len] = x%10 ;
        x = x / 10 ;
    }
    for(int i = len ; i >= 1 ; i --) {
        for(int j = 0 ; j <= 9 ; j ++) {
            cnt[j] += f[i-1] * num[i] ; //第i位之后的每位每个数数都会出现i次
        }
        for(int j = 0 ; j < num[i] ; j ++) {
            cnt[j] += ten[i-1] ;//第i位是x,那么在x之前的都会在出现10^(bit-1)次
        }
        //--------以上只是处理A000000....00这亚子----------//
        //--------以下处理零位--------//
        int num2 = 0 ;
        for(int j = i-1 ; j >= 1 ; j --) {
            num2 = num2 * 10 + num[j] ;//加上零位
        }
        cnt[num[i]] += num2 + 1 ;//
        cnt[0] -= ten[i-1] ;//清除前导零
    }
}
signed main () {
    scanf("%lld%lld",&a,&b) ;
    ten[0] = 1 ;//10的阶乘,每一位代表多少
    for(int i = 1 ; i <= 15 ; i ++) {
        f[i] = f[i-1] * 10 + ten[i-1] ;//在第i位有数字的时候,每个数码有多少个
        ten[i] = 10*ten[i-1] ;
    }
    work(a-1,cnta) ;//work(0-x的各数位,统计答案的数组)
    work(b,cntb) ;
    for(int i = 0 ; i <= 9 ; i ++) printf("%lld ",cntb[i] - cnta[i]) ;
    return 0 ;
}