博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[ZJOI2010]数字计数
阅读量:4933 次
发布时间:2019-06-11

本文共 1463 字,大约阅读时间需要 4 分钟。

题目描述

给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次。

输入输出格式

输入格式:

 

输入文件中仅包含一行两个整数a、b,含义如上所述。

 

输出格式:

 

输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次。

 

输入输出样例

输入样例#1:
1 99
输出样例#1:
9 20 20 20 20 20 20 20 20 20

说明

30%的数据中,a<=b<=10^6;

100%的数据中,a<=b<=10^12。

 

数位DP

 

#include
#include
#include
#include
using namespace std;int a[14];long long bit[14],dp[14][14],ans[10];long long dfs(int dep,int ty,bool lim,int k){ if(!dep) return ty; if(!lim && dp[dep][ty]!=-1) return dp[dep][ty]; long long ans=0; int up= lim ? a[dep] : 9; for(int i=0;i<=up;i++) { if(i==k) ans+=dfs(dep-1,ty+1,lim && i==up,k); else ans+=dfs(dep-1,ty,lim && i==up,k); } if(!lim) dp[dep][ty]=ans; return ans;}int main(){ long long l,r; bit[1]=10; for(int i=2;i<=13;i++) bit[i]=bit[i-1]*10; scanf("%lld%lld",&l,&r); while(r) a[++a[0]]=r%10,r/=10; for(int i=0;i<=9;i++) { memset(dp,-1,sizeof(dp)); ans[i]=dfs(a[0],0,1,i); } l--; if(!l) ans[0]--; int tmp=a[0]; a[0]=0; while(l) a[++a[0]]=l%10,l/=10; for(int i=0;i<=9;i++) { memset(dp,-1,sizeof(dp)); ans[i]-=dfs(a[0],0,1,i); } while(tmp!=a[0]) ans[0]-=bit[--tmp]; printf("%lld",ans[0]); for(int i=1;i<=9;i++) printf(" %lld",ans[i]);}

 

转载于:https://www.cnblogs.com/TheRoadToTheGold/p/7410492.html

你可能感兴趣的文章
关于k-means聚类算法的matlab实现
查看>>
Git分支2
查看>>
一键安装Gitlab后的备份、迁移与恢复
查看>>
因为本人工作繁忙,精力有限,本博客停止更新。有兴趣的博友可以关注我在CSDN上的主博客...
查看>>
SQL server查看触发器是否被禁用
查看>>
[C++基础]在构造函数内部调用构造函数
查看>>
跟随我在oracle学习php(8)
查看>>
Spring 3.1.0 Hibernate 3.0 Eclipse Spring WEB例子
查看>>
UVA-10212 The Last Non-zero Digit. 分解质因子+容斥定理
查看>>
求两个集合的交集,并集,差集
查看>>
Kotlin的语法糖(一)基础篇
查看>>
OkHttp源码分析
查看>>
让你的app体验更丝滑的11种方法!冲击手机应用榜单Top3指日可待
查看>>
windows kernel exploitation基础教程
查看>>
NS_OPTIONS枚举的用法
查看>>
java9系列(九)Make G1 the Default Garbage Collector
查看>>
QAQ高精度模板笔记√
查看>>
Jmeter计数器的使用-转载
查看>>
【Android笔记】入门篇02:全屏设置和禁止横屏竖屏切换
查看>>
Kubernetes的本质
查看>>