(数位DP)51NOD 1042 数字0-9的数量
2024-09-05 22:03:42
给出一段区间a-b,统计这个区间内0-9出现的次数。
比如 10-19,1出现11次(10,11,12,13,14,15,16,17,18,19,其中11包括2个1),其余数字各出现1次。
输入
两个数a,b(1 <= a <= b <= 10^18)
输出
输出共10行,分别是0-9出现的次数
输入样例
10 19
输出样例
1
11
1
1
1
1
1
1
1
1 解:被这道题卡了好久。。。最后自己找了个数模拟了一边流程。
举个例子简单说说:对于数5314,我们可以将它拆分为【5310-5314】【5300-5309】【5000-5299】【0-4999】(注意删去前置0)这几个区间计算,以此得出答案。
#include <stdio.h>
#include <string.h>
#include <math.h> long long num[][],res,a,b; void func(long long *tmp,long long *p,long long power)
{
if (power == ) res = ;
int t = *tmp % ;
if (*tmp == )
{
int n = log10((double)power);
power /= ;
for (int i = ; i < n; ++i) p[] -= * (power /= ) * i;
p[] -= n - ;
return;
}
*tmp /= ;
if (res == ) t++;
long long v= (long long)log10((double)power) * power / * t;
for (int i = ; i >= t; --i) p[i] += v;
for (int i = ; i < t; ++i) p[i] += power + v;
p[t] += res;
res += t * power;
func(tmp, p, power * );
return;
}
int main()
{
while (scanf_s("%lld%lld", &a, &b) != EOF)
{
memset(num, , sizeof num);
a--;
func(&a, num[], );
func(&b, num[], );
for (int i = ; i < ; ++i) printf("%lld\n", num[][i] - num[][i]);
}
return ;
}
当然也可以分别计算0-9的个数,但我不想继续琢磨了。。。
最新文章
- PyQt4入门学习笔记(二)
- WebView cookie 管理
- 彻底理解ThreadLocal二
- 完成卸载vs2010后再安装
- 简单的linux命令笔记
- jQuery下的显示和隐藏
- .net项目IIS、VS 附加进程调试
- c++ 17介绍
- sharepoint 2010 在自定义列表的字段上增加功能菜单
- 【Demo 0007】Java基础-类扩展特性
- js数组之迭代方法
- xctf的一道题目(77777)
- http的CA证书安装(也就是https)
- javascript函数式编程一例分析
- http跳转htts的htaccess文件设置
- js string和number
- jQuery 基础语法
- Session提要
- Python—生成器
- Confluence 6 外部小工具在其他应用中设置可信关系