1049.(*) Counting Ones
2024-10-01 08:02:16
题意:题目大意:给出一个数字n,求1~n的所有数字里面出现1的个数
思路:转自(柳婼 の blog)遍历数字的低位到高位,设now为当前位的数字,left为now左边的所有数字构成的数字,right是now右边的所有数字构成的数字。只需一次次累加对于当前位now来说可能出现1的个数,然后把它们累加即可。a表示当前的个位为1,十位为10,百位为100类推。
对于now,有三种情况:
- 1.now == 0 : 那么 ans += left * a;
- 2.now == 1 : ans += left * a + right + 1;
- 3.now >= 2 : ans += (left + 1) * a;
从排列组合的角度分析会显得容易些。比如now==1时,当前位出现1时,左边的数字可能小于left也可能等于left。
- 1、小于left时,左边共left种可能,now右边的数字是任意的,共有a种可能,a=(10^now右边的数的位数)。因为now左边小于left,无论now右边的数字如何,整个数字一定属于1~n范围的
- 2、等于left时,左边只有一种可能,now的数不能是任意的了,只能在0~right变化。
以上两种情况相加,即now为1时,共left * a + right + 1种
代码:
#include <iostream>
using namespace std;
int main() {
int n, left = , right = , a = , now = , ans = ;
scanf("%d", &n);
while(n / a) {
left = n / (a * ), now = n / a % , right = n % a;
if(now == ) ans += left * a;
else if(now == ) ans += left * a + right + ;
else ans += (left + ) * a;
a = a * ;
}
printf("%d", ans);
return ;
}
最新文章
- opencv常见代码
- jquery 高度的获取
- 如何通过XShell传输文件
- XXX项目 android 开发笔记
- IBM Appscan基本操作手册
- 按 Eclipse 开发喜好重新布置 cocos2dx 目录层次
- sql定期移植数据的存储过程
- Spring事务操作介绍
- es6 promise对象
- 爬取小说 spider
- .net 基础
- linux添加磁盘空间
- 记webpack下提取公共js代码的方法
- iOS webservice 接口使用方法
- scrapy框架系列 (4) Scrapy Shell
- [na]TCP的三次握手四次挥手/SYN泛洪
- iOS:scale image
- CSS3实现两行或三行文字,然后多出的部分省略号代替
- activeX 开发
- 面向英特尔&#174; x86 平台的 Unity* 优化指南: 第 1 部分