数位dp学习笔记

yyrwlj · 2023-08-21 05:24:43 · 算法·理论

参考题目

对于每个 (a, b) ，可以把 0-9 每个数字都处理一遍。

定义 count(n, x) 函数，代表 1-n 中, x 出现的次数。

那么, count(b, x) - count(a - 1, x) 即为答案。

如何快速的求出 count(n, x) 呢？

先假设 n 是个 7 位数 (n = abcdefg)，求 1 出现的次数。

可以枚举每一位 x 出现的次数，然后求和。

假设现在枚举到第 4 位数，也就是 d 所在的位置。

答案就是所有合法的 xxx1yyy 的数量。

这里分情况进行讨论。

1. 000 \le xxx < abc

这种情况下，无论 yyy 选什么都一定合法。

所以贡献为 abc \times 1000 （ xxx 可以是 000-abc ， yyy 可以是 000-999 ）。

2. xxx = abc

在此基础上，还需继续深入讨论。

2.1 d < 1

这种情况下无论 yyy 选什么都不合法，所以有 0 种可能。

2.2 d = 1

这种情况下 yyy 的取值范围在 000-efg ，所以贡献为 efg+1 。

2.3 d > 1

这种情况下 yyy 的取值范围在 000-999 ，所以贡献为 1000 。

以此类推，其它情况可以照葫芦画瓢，但还有一些特殊情况。

特殊情况一：当前枚举的位置是最高位

这样 1. 就不存在了，也就为 0 。

特殊情况二：当前找的数字为 0

在这种情况下，2.部分不变，需要注意1.部分。

如果 xxx=000 的话，当前看的这一位和左面都会被忽略掉，所以 xxx 的取值范围应变为 001-abc，贡献为 (abc-1) \times 1000。

最后附上AC代码。

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
int get(vector<int> num,int l,int r)
{
    int ans = 0;
    for (int i=l;i>=r;i--)
        ans = ans * 10 + num[i];
    return ans;
}
int Pow(int x)
{
    int ans = 1;
    while (x--)
        ans *= 10;
    return ans;
}
int count(int n,int x)
{
    if (n == 0)
        return 0;
    vector<int> num;
    while (n)
    {
        num.push_back(n % 10);
        n /= 10;
    }
    n = num.size() - 1;
    int ans = 0;
    for (int i = n - (x == 0); i >= 0; i --)
    {
        if (i != n)
        {
            ans += get(num, n, i + 1) * Pow(i);
            if (x == 0)
                ans -= Pow(i);
        }
        if (num[i] == x)
            ans += get(num, i - 1, 0) + 1;
        else if (num[i] > x)
            ans += Pow(i);
    }
    return ans;
}
int main()
{
    for (;;)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if (a == 0)
            break;
        if (a > b)
            swap(a, b);
        for (int i=0;i<9;i++)
            printf("%d ", count(b, i) - count(a - 1, i));
        printf("%d\n", count(b, 9) - count(a - 1, 9));
    }
    return 0;
}