TZOJ 2478 How many 0's?(数位DP)
描述
A Benedict monk No.16 writes down the decimal representations of all natural numbers between and including m and n, m ≤ n. How many 0's will he write down?
输入
Input consists of a sequence of lines. Each line contains two unsigned 32-bit integers m and n, m ≤ n. The last line of input has the value of mnegative and this line should not be processed.
输出
For each line of input print one line of output with one integer number giving the number of 0's written down by the monk.
样例输入
10 11
100 200
0 500
1234567890 2345678901
0 4294967295
-1 -1
样例输出
1
22
92
987654304
3825876150
题意
求[l,r]之间0的个数。
题解
数位DP。
[l,r]转化后变成[0,r]-[0,l-1]。
由于从0开始不好处理,可以变成从1开始,然后特判一下0。
考虑每一位数的贡献,比如1234,固定第3位为0的贡献:
1.0为头,00,01,02,03,04,前导0不考虑(除0外的数要考虑这个情况)。
2.0为尾,贡献就是12*10^1=120,意思就是0前面共有1-12(12个数),0后面有0-9(10个数)。
代码中注释的是求0-9的个数。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[],b[],l,r;
void dp(ll t,ll *c,ll d)
{
ll n=t/,m=t%,temp=n;
//for(int i=1;i<=m;i++)c[i]+=d;
//for(int i=0;i<=9;i++)c[i]+=d*n;
c[]+=d*n;
while(temp)
{
c[temp%]+=(m+)*d;
temp/=;
}
if(n)dp(n-,c,d*);
} int main()
{
while(scanf("%lld%lld",&l,&r)!=EOF)
{
if(l==-&&r==-)break;
memset(a,,sizeof(a));
memset(b,,sizeof(b));
dp(l-,a,);
dp(r,b,);
if(l==)b[]++;
printf("%lld\n",b[]-a[]);
}
return ;
}
最新文章
- Event的Propagate
- pod 安装总结
- 印刷电路板(PCB)的材料
- virtualbox macosx10.9改变分辨率方法
- 我的这10年——从机械绘图 到 炼油 到 微软MVP 的华丽转身
- 【JavaScript学习笔记】鼠标样式
- js数组的管理[增,删,改,查]
- Asp.Net Core Authentication Middleware And Generate Token
- SQL Server查询中对于单列数据&#39;,&#39;分割的数据进行的拆分操作,集合的每一个行变多行
- [Kubernetes]资源模型与资源管理
- 测试框架httpclent 1.HttpClient简介及第一个demo
- Express全系列教程之(五):Express的中间件
- [LeetCode] 120. Triangle _Medium tag: Dynamic Programming
- 位运算符&;与、或|、异或^
- mac idea中的文件在finder中打开
- shell实现自动部署两台tomcat项目+备份
- ZOJ 3963 Heap Partition(multiset + stl自带二分 + 贪心)题解
- mysql数据类型长度
- 【LeetCode】41. First Missing Positive (3 solutions)
- docker的安装以及jdk和tomcat的环境配置