用dp[pos][val][cnt]表示状态,pos是数位,val是当前统计的数字,cnt是目前统计的目标数字的出现次数

注意状态的转移过程,统计数字0时前导0的影响。

 1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 typedef long long LL;
6 int dig[15],pos;
7 LL dp[15][10][15],ans[2][10];
8
9 LL dfs(int pos,int val,int cnt,bool lead,bool limit){
10 if(pos==0) return cnt;
11 if(!limit&&!lead&&dp[pos][val][cnt]!=-1) return dp[pos][val][cnt];
12 int len=limit?dig[pos]:9,t=0;
13 LL ans=0;
14 for(int i=0;i<=len;i++){
15 if(val!=i) t=cnt;
16 else{
17 if(lead&&val==0) t=0;
18 else t=cnt+1;
19 }
20 ans+=dfs(pos-1,val,t,lead&&i==0,limit&&i==len);
21 }
22 if(!limit&&!lead) dp[pos][val][cnt]=ans;
23 return ans;
24 }
25
26 void solve(LL x,int idx){
27 if(x==0) return ;
28 int pos=0;
29 while(x){
30 dig[++pos]=x%10;
31 x/=10;
32 }
33 for(int i=0;i<10;i++)//对每一个数字分别求解
34 ans[idx][i]=dfs(pos,i,0,1,1);
35 }
36
37 int main(){
38 memset(dp,-1,sizeof(dp));
39 LL a,b;
40 while(~scanf("%lld%lld",&a,&b),a+b){
41 if(a>b) swap(a,b);
42 memset(ans,0,sizeof(ans));
43 solve(a-1,0),solve(b,1);
44 for(int i=0;i<10;i++)
45 printf("%lld ",ans[1][i]-ans[0][i]);
46 printf("\n");
47 }
48 return 0;
49 }

最新文章

  1. 【工具】VS2010常用调试技巧(1)
  2. poj3250
  3. Bootstrap库之Modals
  4. Servlet基础(三) Servlet的多线程同步问题
  5. Ajax提交整个表单
  6. OV7725学习(二)
  7. oracle-7参数文件的管理
  8. jQuery 源码分析5: jQuery 基本静态方法(一)
  9. 更改Altium中PCB大小/精确确定板子尺寸
  10. SpringMVC全注解
  11. SpringMVC 学习-如何搭配使用 Velocity 页面模板
  12. HTTP客户端识别与Cookie机制
  13. 最强大的跨语言调用生成工具:Swig 快速实用教程
  14. [转]Mysql FROM_UNIXTIME as UTC
  15. [算法导论]插入排序 @ Python
  16. TCP连接图示
  17. Android 经典欧美小游戏 guess who
  18. (笔记)Linux下的ioctl()函数详解
  19. 高斯混合模型Gaussian Mixture Model (GMM)
  20. WebDriverAPI(8)

热门文章

  1. 浅谈hooks——useEffect
  2. 面试题:Java中为什么只有值传递?
  3. 在阿里云Centos7.6上面部署基于Redis的分布式爬虫Scrapy-Redis
  4. 青山不遮,毕竟东流,集成Web3.0身份钱包MetaMask以太坊一键登录(Tornado6+Vue.js3)
  5. 用虚拟机封装win10系统的一些记录
  6. Luogu1083 借教室 (线段树)
  7. Oracle-DDL,DML理解以及应用
  8. zabbix 报表动作日志 报错”503“
  9. wbr 文本换行规则标签
  10. ZZH与计数(矩阵加速,动态规划,记忆化搜索)