P2602 [ZJOI2010]数字计数（递推）

P2602 [ZJOI2010]数字计数

思路：

首先考虑含有前导0的情况，可以发现在相同的\(i\)位数中，每个数的出现次数都是相等的。所以我们可以设\(f(i)\)为\(i\)位数每个数的出现次数。

那么就有递推方程：\(f(i)=f(i-1)*10+10^{i-1}\)。

假设现在要求的数为\(x\)位，那么我们依次从\(x\)位往下面求就行了。假设第\(x\)位的数字为\(k\)，那么我们枚举第一位从\(0\)到\(k\)，每一个数字的出现次数加上\(f(i-1)*k+10^{i-1}\)，同时\(k\)这个数还会有多出现的情况，计算一下就行了。就这样一位一位来算就ok了。

因为我们之前没有考虑前导0的情况，所以我们减去多算上的情况就行了。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 15;

ll f[N], cnta[N], cntb[N], pow10[N];

ll a, b;

int tot;

ll num[N] ;

void solve(ll x, ll *cnt) {

    tot = 0;

    ll tmp = x;

    while(x) {

        num[++tot] = x % 10;

        x /= 10;

    }

    for(int i = tot; i >= 1; i--) {

        for(int j = 0; j < 10; j++) cnt[j] += num[i] * f[i - 1] ;

        for(int j = 0; j < num[i]; j++) cnt[j] += pow10[i - 1] ;

        tmp -= num[i] * pow10[i - 1] ;

        cnt[num[i]] += tmp + 1;

        cnt[0] -= pow10[i - 1] ;

    }

}

int main() {

    pow10[0] = 1;

    ll t = 0;

    for(int i = 1; i < N; i++) {

        f[i] = f[i - 1] * 10 + pow10[i - 1] ;

        pow10[i] = pow10[i - 1] * 10;

    }

    cin >> a >> b;

    solve(a - 1, cnta) ;

    solve(b, cntb) ;

    for(int i = 0; i < 10; i++) cout << cntb[i] - cnta[i] << ' ';

    return 0;

}

巴特西

P2602 [ZJOI2010]数字计数（递推）

P2602 [ZJOI2010]数字计数

思路：

最新文章

热门文章