pat1049. Counting Ones (30)
2024-10-19 03:35:22
1049. Counting Ones (30)
时间限制
10 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue
The task is simple: given any positive integer N, you are supposed to count the total number of 1's in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1's in 1, 10, 11, and 12.
Input Specification:
Each input file contains one test case which gives the positive N (<=230).
Output Specification:
For each test case, print the number of 1's in one line.
Sample Input:
12
Sample Output:
5
思路:
统计每位的1的贡献。
对于k位(k>=1):
1.Ak=0,count+=AnAn-1....Ak+1AkAk-1....A1*10^(k-1)
2.Ak=1,count+=AnAn-1....Ak+1AkAk-1....A1*10^(k-1)+Ak-1Ak-2...A1+1
3.Ak>=2,count+=(AnAn-1....Ak+1AkAk-1....A1+1)*10^(k-1)
#include<cstdio>
#include<stack>
#include<cstring>
#include<iostream>
#include<stack>
#include<set>
#include<map>
using namespace std;
//count的最大值是1036019223
int main(){
int n;
scanf("%d",&n);
long long base=;
long long count=;
int frpart,afpart,a;
while(n>=base){
a=n/base%;
frpart=n/(*base);
afpart=n%base;
count+=frpart*base;
if(a==){
count+=afpart+;
}
else if(a>){
count+=base;
}
base*=;
}
printf("%lld\n",count);
return ;
}
最新文章
- 怎么可以让div自适应屏幕的高度?(已解决)
- 装饰模式(Decorate Pattern)
- Jade之Case
- MyBatis知多少(10)应用程序数据库
- JAVA基础知识之JVM-——URLClassLoader
- CF 486D vailid set 树形DP
- Android中解析JSON形式的数据
- iOS开发--绘图教程
- NOI题库7624 山区建小学(162:Post Office / IOI2000 POST OFFICE [input] )
- Android的线程和线程池
- Window2003、xp远程备份数据库文件(xcopy+rar+pscp)
- App 组件化/模块化之路——Repository 模式
- 玩转Ecs服务器之搭建Ftp
- 【原】Java学习笔记025 - 内部类
- 为什么使用Nosql:Nosql和SQL的区别
- ansible笔记(7):常用模块之系统类模块
- laravel 模型事件 updated 触发条件
- 二叉树转换成森林&;amp;森林变成二叉树
- main方法之args参数
- Shrio第一天——入门与基本概述