Acwing 338. 计数问题(数位DP)

题意:

给你一段区间[a, b]，请你求出这段区间0~9的个数。

思路：

对于求一段区间是否满足一定条件的个数这种问题。我们可以一眼看出是数位DP问题。
那么对于数位DP问题我们通常应该怎么去处理呢。

技巧1：我们假设对于区间[1,n]满足条件的总个数我们用f[n]表示，那么对于区间[a,b]的个数显然我们是可以用前缀和的思想，f[a,b] = f[b] - f[a-1]；
技巧2：我们可以采用树形结构对每种情况进行分类讨论，对于技巧2后面的题我们会提到。

那么对于数位DP最根本的东西就是分类讨论
感谢yxc！

对于本题来说，我们如何去求1~N中0 ~ 9的个数呢？首先我们假设N是一个七位数我们用abcdefg表示每一位数是多少？现在我们举例求第4位为1的有多少种。

那么下面我们来进行分类讨论：
首先目前我们就是来讨论 1 ≤ x x x 1 y y y ≤ a b c d e f g 1 \le xxx1yyy \le abcdefg 1≤xxx1yyy≤abcdefg有多少个数满足上述请款。
1：当前三位的范围是 ( x x x ∈ [ 000 , a b c − 1 ] ) (xxx \in [000,abc-1]) (xxx∈[000,abc−1]) 的话，那么对于这种情况我的xxx1yyy就有abc * 1000 = abc*10^3个数。
2：当前三位数是abc的话，那么就有以下三种情况：
\ \ \ 2.1 如果d<1的话那么一定找不到因为我们现在求得是d位1的请情况。
\ \ \ 2.2 如果d=1的话那么现在就是abc1yyy那么对于这种情况的话他的总方案数就是[000,efg]也就是有efg+1个数
\ \ \2.3 如果d>1的话那么后三位随便取就有[000,999]种数也就是 1000 = 1 0 3 1000=10^3 1000=103
所以对于 [1,abcdefg] 中第四位为1的总方案数就是 a n s = a b c ∗ 1 0 3 + e f g + 1 + 1 0 3 ans = abc*10^3 + efg+1+10^3 ans=abc∗103+efg+1+103
那么对于其他位置其他数的求法与上面大同小异了。但是这儿有一个地方要特别注意就是对于 统计0的时候我们是不允许出现前置0的。所以对于我们的第一种情况就不是[000,abc-1]而是[001,abc]。

代码

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define int long long
#define endl "\n"

using namespace std;

const int N = 2e5 + 10;

int ksm(int b)
{
    int a = 10;
    int ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

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 count(int n, int x)
{
    if(!n) return 0;
    vector<int> num;

    while(n)
    {
        num.push_back(n % 10);
        n /= 10;
    }

    n = num.size();

    int res = 0;
    for(int i = n - 1 - !x; i >= 0; i --)
    {
        if(i < n-1)
        {
            res += get(num, n-1, i+1) * ksm(i);
            if(!x) res -= ksm(i);
        }

        if(num[i] == x) res += get(num, i-1, 0) + 1;
        else if(num[i] > x) res += ksm(i);
    }

    return res;
}

signed main()
{
    IOS;
    int a, b;
    while(cin >> a >> b, a || b)
    {
        if(a > b)swap(a, b);

        for(int i = 0; i < 10; i ++)
            cout << count(b, i) - count(a-1, i) << " ";
        cout << endl;
    }
    return 0;
}