数位统计DP AcWing 338. 计数问题

男娘i 2023-09-28 13:03 73阅读 0赞

## 数位统计DP AcWing 338. 计数问题 ##

### 原题链接 ###

[AcWing 338. 计数问题][AcWing 338.]

### 思路 ###

对于数字n每位数出现数字x进行分类讨论  
此处以第四位d为例  
![在这里插入图片描述][4045ae786ee4490e97243d69cbc3e676.png]  
详细过程见代码

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>=b;--i)
    using namespace std;
    const int N = 15;
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    int pow(int x){
        int res=1;
        while(x--){
            res*=10;
        }
        return res;
    }
    // 获取数组a第r位至第l位数字
    int get(vector<int> a, int l, int r){
        int res=0;
        Rep(i, l, r){
            res=res*10+a[i];
        }
        return res;
    }
    // 1至n中x出现的次数
    int cnt(int n, int x){
        if(!n){
            return 0;
        }
        else{
            vector<int> a;
            while(n){
                a.push_back(n%10);
                n/=10;
            }
            int res=0;
            n=a.size();
            // 若x为0 n-2->0 由于最高位不能位0, 故应该从n-2开始
            // 若x非0 n-1->0
            Rep(i, n-1-!x, 0){
                // 前i位数(即abc)构成小于n数字中x出现次数
                if(i<n-1){
                    res+=(get(a, n-1, i+1))*pow(i);
                    // 去除前i位数都为零个数
                    if(!x){
                        res-=pow(i);
                    }
                }
                // 第i位之后(即efg)小于n数字中x出现次数
                if(a[i]==x){
                    res+=get(a, i-1, 0)+1;
                }else if(a[i]>x){// 第i位后全部数字个数
                    res+=pow(i);
                }
            }
            return res;
        }
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int a, b;
        while(a=read(), b=read(), a){
            if(a>b){
                swap(a, b);
            }
            rep(i, 0, 10){
            	// a到b中i出项次数
                printf("%lld ", cnt(b, i)-cnt(a-1, i));
            }
            puts("");
        }
        return 0;
    }

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 338.]: https://www.acwing.com/problem/content/340/
[4045ae786ee4490e97243d69cbc3e676.png]: https://img-blog.csdnimg.cn/4045ae786ee4490e97243d69cbc3e676.png
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png