首页 > 代码库 > 51nod 1042 数字0-9的数量 (数位dp、dfs、前导0)
51nod 1042 数字0-9的数量 (数位dp、dfs、前导0)
1042 数字0-9的数量
基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题
收藏
关注
取消关注
给出一段区间a-b,统计这个区间内0-9出现的次数。
比如 10-19,1出现11次(10,11,12,13,14,15,16,17,18,19,其中11包括2个1),其余数字各出现1次。
Input
两个数a,b(1 <= a <= b <= 10^18)
Output
输出共10行,分别是0-9出现的次数
Input示例
10 19
Output示例
1
11
1
1
1
1
1
1
1
1
终于过了,前导零太烦了。
#include <iostream> #include <cstring> using namespace std; typedef long long ll; ll ten[20]={1},a[20],dp[20]; void init() { for(ll i=1;i<20;i++) ten[i]=ten[i-1]*10; } ll dfs(ll pos,ll num,ll lead,ll limit,ll who) { if(pos==-1) return num; if(!limit&&dp[pos]!=-1&&!lead) return num*ten[pos+1]+dp[pos]; ll up=limit?a[pos]:9; ll tmp=0; if(who!=0) for(int i=0;i<=up;i++) tmp+=dfs(pos-1,num+(who==i),0,limit&&a[pos]==i,who); else for(int i=0;i<=up;i++) tmp+=dfs(pos-1,num+(who==i&&!lead),lead&&i==0,limit&&a[pos]==i,who); if(!limit&&!lead) dp[pos]=tmp; return tmp; } ll solve(ll n,ll m) { ll pos=0; while(n) { a[pos++]=n%10; n/=10; } return dfs(pos-1,0,1,1,m); } int main() { ll x,y; ios::sync_with_stdio(false); init(); cin>>x>>y; for(ll i=0;i<=9;i++) { memset(dp,-1,sizeof(dp)); cout<<solve(y,i)-solve(x-1,i)<<endl; } return 0; }
51nod 1042 数字0-9的数量 (数位dp、dfs、前导0)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。