当前位置: 代码迷 >> 综合 >> 51Nod 1042 数字0-9的数量(数位dp)
  详细解决方案

51Nod 1042 数字0-9的数量(数位dp)

热度:14   发布时间:2023-11-08 15:28:19.0

参考自:这里写链接内容

#include <iostream>
#include<algorithm>
#include<cmath>
#define maxn 1e5+10
typedef long long ll;
using namespace std;
ll ans[10];         //保存小于n,数字i出现的次数void solve(ll n,int sign){ll cur,pre,after,tmp=1,tn=n;while(n){cur=n%10;pre=n/10;after=tn-n*tmp;for(int i=0;i<10;i++){if(cur>i){ans[i]+=(pre+1)*tmp*sign;}else if(cur<i){ans[i]+=pre*tmp*sign;}else{ans[i]+=(pre*tmp+after+1)*sign;}}ans[0]-=tmp*sign;  //减去一个前导0tmp*=10;n/=10;}
}int main(){ll l,r;cin>>l>>r;solve(l-1,-1);solve(r,1);for(int i=0;i<10;i++){cout<<ans[i]<<endl;}return 0;
}