数位 dp 入门

如果余生有浪漫的星河，日子慢慢过。《如果我们在余生相遇》

现在发现我们理解一件事情，其实是基于我们的认知去理解的。所以一些以前理解不了的事情，或者说当时难以理解的事情，过一段时间，再去看，可能恍然大悟。

#include<iostream>
#include<algorithm>
#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 pow10(int x){
    int ans=1;
    while(x--){
        ans*=10;
    }
    
    return ans;
}

int count(int n,int x){
    vector<int> num;
    while(n){
        num.push_back(n%10);
        n/=10;
    }
    n=num.size();
    
    int ans=0;
    for(int i=n-1-!x;i>=0;i--){
        if(i<n-1){
            ans+=get(num,n-1,i+1)*pow10(i);
            if(!x){
                ans-=pow10(i);
            }
        }
        
        if(x==num[i]){
            ans+=get(num,i-1,0)+1;
        }else if(x<num[i]){
            ans+=pow10(i);
        }
    }
    
    return ans;
}

int main(){
    int a,b;
    while(scanf("%d%d",&a,&b),a){
        if(a>b){
            swap(a,b);
        }
        
        for(int i=0;i<10;i++){
            printf("%d ",count(b,i)-count(a-1,i));
        }
        puts("");
    }
    
    return 0;
}

今天感觉自己的状态不好。这题写半天，理解半天才搞清楚。走神看了一下 b 站视频，凯圣王讲健身的质量是比重要更加重要的。健身房关门了。我好想健身。我们学习也是质量大于数量或者速度。慢才能稳，稳才能快。很多事情其实是很漫长的一个过程。我在操场看到有大体重的人在跑步，我就在想，假设他真的想要减重的话，一定不能跑得太快了，因为心态是最重要的。跑太快了人根本顶不住的。

数位 dp 其实就是有点前缀和的思想在里面。我们要求 a 到 b 的所有数字里面的 0~9 的出现次数，那么我们求出来前缀和，然后用前缀和公式可以计算。这是第一步转换。第二步转换是，我们考虑把上界的数字存到向量里面，其实就是数组。没差。然后我们分情况来考虑。首先是枚举位左边的数字。假设枚举位左边的数字比原来的数字小，那么枚举位右边的数字可以随便选。比如说枚举位右边有三位数字，那么可以有 1000 1000 1000 种情况。然后乘以枚举位左边的可能的情况数目。但是这个时候需要特别考虑 x=0 的情况。因为，不能有前导零。也就是说，假设我们当前枚举的情况是 0 0 0 ，那么前面那位就不可以是零。好吧。其实这个我不是太理解。大概懂这个意思。然后就是其他的情况。其实也比较简单。写的时候注意下标。写 get 函数的时候，注意，l 是大于 r 的，不然很容易写错，还发现不了。