Uva1640(统计数字出现的次数)
2024-10-08 08:11:51
题意:
统计两个整数a,b之间各个数字(0~9)出现的次数,如1024和1032,他们之间的数字有1024 1025 1026 1027 1028 1029 1030 1031 1032 总共有10个0,10个1,3个3等等。
解法:
这类问题的一般步骤都是先用f(n,d)计算出0~n中d数字出现的次数,那么答案就是f(b,d)-f(a-1,d)
下面程序中的注释为(1,2974)的第一层(未递归)解释,递归后同理
1-2974 拆分为1-2970 和 2971-2974
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int l, r;
int a[], b[]; void solve(int n, int m) {
int x = n / ;//除了末位以外的 x=297
int y = n % ;//最后一位的数字范围 y=4
int tmp = x;
//计算小于10*x+1到10*x+y中个位数的个数,b[1-y]也就是(2971-2974)个位数
for (int i = ; i <= y; i++)b[i] += m;
//计算10*x-10到10*x-1中个位数的总个数,296 0-296 9 个位数个数每个都是296个
for (int i = ; i <= ; i++)b[i] += m*x;
while (tmp) {
//10*x 到10*x+y非个位的个数,因为从0开始,所以*(y+1)就是非个位位数,当然还要乘m
b[tmp % ] += m*(y + );
tmp /= ;
}
if (x) solve(x - , m * );
} int main() {
while (cin >> l >> r && (l || r)) {
memset(b, , sizeof(b));
if (l > r)swap(l, r);
solve(l - , );
for (int i = ; i <= ; i++)a[i] = b[i], b[i] = ;
solve(r, );
cout << b[] - a[];
for (int i = ; i <= ; i++)cout << " " << b[i] - a[i];
cout << endl;
}
return ;
}
最新文章
- html5 与视频
- 【转】Python实现不同格式打印九九乘法表
- CentOS 7安装Mysql并设置开机自启动
- tomcat安全配置
- [AaronYang]C#人爱学不学[4]
- setTimeout方法
- A Tour of Go For
- boost库----enable_shared_from_this类的作用和实现原理
- Go语言Web框架gwk介绍 1
- 调用start()方法和直接调用run()方法的区别
- Windows 10中Oracle数据库导出到Access数据库(MDB)
- CAS SSO单点登录实例
- HTML 页面meta标签
- css font-family常用的黑体宋体等字体中英文对照
- 正则匹配URL地址
- 一句话木马:ASP篇
- PyCharm2018激活码
- js原码工具集
- HslCommunication库的二次协议扩展,适配第三方通讯协议开发,基础框架支持长短连接模式
- Backup Log
热门文章
- [Python源码剖析]字符缓冲池intern机制
- Pycharm创建Django项目显示python non-zero exit code(1)错误
- 题解【RQNOJ PID497 0/1字串问题】
- 题解 UVA1479 【Graph and Queries】
- TestStand 基础知识[6]--Build-in Step Types (1)
- light oj 1067 费马小定理求逆元
- axios中get请求的params参数中带数组的处理方法
- Linux下通过二进制方式安装mysql5.7版本和系统优化
- dotnetcore3.1 WPF 实现多语言
- a链接四种伪类状态切换实现人机交互