问m~n之间的数中共有多少个0,过程稍稍麻烦了一些,半天的时间才搞定。

直接上码吧

/*************************************************************************
> File Name: 11038_数位DP.cpp
> Author: Chierush
> Mail: qinxiaojie1@gmail.com
> Created Time: 2013年06月16日 星期日 16时13分54秒
************************************************************************/ #include <iostream>
#include <cstring>
#include <cstdlib>
#include <set>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm> #define LL long long
#define LLU unsigned long long using namespace std; LL g(char *s)
{
LL ans=0;
for (int i=1;i<strlen(s);++i)
ans=ans*10+s[i]-'0';
return ++ans;
} LL f[12],Count[12],sum[12],sbit[12];
char s[12]; LL dp(LL n)
{
if (n<0) return 0;
if (n<10) return 1;
LL ans=0;
sprintf(s,"%lld",n);
ans+=sum[strlen(s)-1]+(s[0]-'1')*(sum[strlen(s)-1]+sbit[strlen(s)-1]);
//printf("---%lld\n",ans);
for (int i=1;i<strlen(s)-1;++i)
if (s[i]>'0')
{
ans+=(sum[strlen(s)-i-1]+sbit[strlen(s)-i-1])*(s[i]-'1');
ans+=Count[strlen(s)-i-1]+sum[strlen(s)-i-1]+sbit[strlen(s)-i-1];
}
else
ans+=g(s+i);
return ++ans;
} int main()
{
Count[1]=10;
for (int i=2;i<=10;++i)
Count[i]=Count[i-1]*10;
for (int i=2;i<=10;++i)
sbit[i]=Count[i-1]+sbit[i-1];
sum[1]=f[1]=1;
for (int i=2;i<=10;++i)
f[i]=9*(sum[i-1]+sbit[i-1]),sum[i]=sum[i-1]+f[i];
LL n,m;
//printf("%lld\n",dp(500));
while (scanf("%lld%lld",&m,&n) && m>=0)
printf("%lld\n",dp(n)-dp(m-1));
return 0;
}

  

最新文章

  1. DatePicker及其监听
  2. setObject()用法
  3. jelq
  4. python基础——装饰器
  5. Sublime Text对Python代码加注释的快捷键
  6. 1.1Linux 系统简介(学习过程)
  7. nodejs技术面试问题整理
  8. [linux] linux 破解版confluence安装
  9. C++学习笔记:List容器
  10. 在QTableView中使用各种自定义委托
  11. video视频铺满
  12. 基于python的统计公报关键数据爬取
  13. shell版的nginx安装
  14. LoadRunner-参数化(参数间关联)
  15. iOS UI-创建空项目
  16. php session阻塞页面分析及优化 (session_write_close session_commit使用)
  17. 2018.08.30 bzoj4318: OSU!(期望dp)
  18. fork函数和vfork函数的区别--19
  19. 团体程序设计天梯赛L1-019 谁先倒 2017-03-22 17:35 33人阅读 评论(0) 收藏
  20. dede 后台登录以后一片空白

热门文章

  1. Android studio怎么创建Android虚拟机?
  2. POJ 3904(容斥原理)
  3. 矩阵微分(matrix derivatives)
  4. node lesson2
  5. HDU 2842 Chinese Rings(矩阵高速功率+递归)
  6. 希尔伯特空间(Hilbert Space)
  7. BIOS 选项设置的含义
  8. JQUERY名称冲突
  9. 使用HANDLE_MSG宏简化Win32应用的开发
  10. 基于IdentityServer4的单点登录——IdentityServer