【题解】P2602 数字计数

P2602 [ZJOI2010]数字计数

题目描述

给定两个正整数 (a) 和 (b) ，求在 ([a,b]) 中的所有整数中，每个数码(digit)各出现了多少次。

输入格式

输入文件中仅包含一行两个整数(a,b)，含义如上所述。

输出格式

输出文件中包含一行 (10) 个整数，分别表示 (0-9) 在 ([a,b]) 中出现了多少次。

说明/提示

(30\%)的数据中，(a<=b<=10^6)；

(100\%)的数据中，(a<=b<=10^{12})。

Solution

此题解仅讲想法，不讲有关数位 (dp)的基础知识或写法，如果还没有学过数位 (dp) 的可以先看别的题目

看到题解里用 (dfs) 做的都是设的两维或以上的状态，实际上这道题只需要一维状态就够了

设目前已经填到了第 (pos) 位，则不管 (num -!- pos + 1) 位上填的是什么，之后的 (1 -!- pos)位上的贡献是不变的（除非是已经到了 (limit) 的限制了，这个之后再讨论）

那么状态很明显为 (f[pos])

(eg:)现在要填五位的数，目前状态为 (12XXX)， (limit) 为 (30000)，则后面的三位可以直接由 (f[3]) 转移过来，因为这属于子结构，不对前面造成影响

为什么可以这样转移？

前面所填的数（类似于 (eg) 中的 (12XXX) 的 (12)）的贡献如何计算？

我们可以发现，对于 (12XXX) 中第四位上的 (2) 的贡献，是 (10^{pos - 1}) 的。因为 (12XXX) 的后三位可以填 (000) - (999) 中的任意一种，则第四位的 (2) 就被计算了 (10^3) 次，即贡献就是 (10^{pos - 1})。注意：这里所讨论的 (2) 的贡献值，仅考虑第四位上的 (2) ，对于后面位置上的为子结构，在之后会考虑到，而前面位置上的，在之前已经预先考虑过了，所以不会重复也不会漏情况。

现在再来讨论 (limit) 的限制情况。

假设将 (eg) 中的 (limit) 改为 (12300)，则填后三位时就只能填 (000) - (300)，总共是 (12300 - 12000 + 1) 种，于是只用在计算贡献时加这样一个判断就可以了。

Code

#include<bits/stdc++.h>
#define ll long long
#define F(i, x, y) for(int i = x; i <= y; ++ i)
using namespace std;
const int N = 15;
ll L, R;
int cnt[N];
ll f[N];
ll add(int pos)//计算lim限制时的贡献
{
    ll ans = 0;
    for(int i = pos - 1; i >= 1; -- i) ans = ans * 10 + cnt[i];
    return ans + 1; 
}
ll dp(int pos, int x, int lim, int last)
{/* pos为第几位  x为现在在算的数码
	lim为是否为限制 last为上一次的值（处理前导零）*/
    if(! pos) return 0;
    if(! lim && f[pos] != -1 && last != 10) return f[pos];
    ll ret = 0;
    F(i, (last == 10 ? 1 : 0), (lim ? cnt[pos] : 9))
    {
        if(i == x && (i != cnt[pos] || ! lim)) ret += pow(10, pos - 1);
        else if(i == x) ret += add(pos);//分情况计算贡献
        ret += dp(pos - 1, x, lim && i == cnt[pos], i);
    }
    if(last == 10) ret += dp(pos - 1, x, 0, last);
    if(! lim) f[pos] = ret;
    return ret;
}
ll work(int x, ll r)
{
    memset(f, -1, sizeof(f));
    int num = 0;
    for(r; r; r /= 10) cnt[++ num] = r % 10;
    return dp(num, x, 1, 10);
}
int main()
{
    cin >> L >> R;
    F(i, 0, 9) printf("%lld ", work(i, R) - work(i, L - 1));
    printf("
");
    return 0;
}

Thanks

如果有任何疑问欢迎提出或和我一起讨论(′▽`〃)