文档章节

PAT A1049. Counting Ones (30)

 阿豪boy
发布于 2016/11/12 16:10
字数 498
阅读 24
收藏 0
点赞 0
评论 0

1049. Counting Ones (30)

https://www.patest.cn/contests/pat-a-practise/1049

时间限制

100 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

题目大意:给出一个数字n,求1~n的所有数字里面出现1的个数
分析:这是一道数学问题。从第一位(个位)到最高位,设now为当前位的数字,left为now左边的所有数字构成的数字,right是now右边的所有数字构成的数字。只需要一次次累加对于当前位now来说可能出现1的个数,然后把它们累加即可。a表示当前的个位为1,十位为10,百位为100类推。
对于now,有三种情况:
1.now == 0 : 那么 ans += left * a; //因为now==0说明now位只有在left从0~left-1的时候会产生1,所以会产生left次,但是又因为右边会重复从0~999…出现a次
2.now == 1 : ans += left * a + right + 1;//now = 1的时候就要比上一步多加一个当now为1的时候右边出现0~right个数导致的now为1的次数
3.now >= 2 : ans += (left + 1) * a;//now大于等于2就左边0~left的时候会在now位置产生1,所以会产生left次,但是又因为右边会重复从0~999…出现a次

#include <iostream>
#include <cstdio>
using namespace std;
int main(int argc, char *argv[]) {
	int n, a = 1, ans = 0;
	int left, now, right;
	scanf("%d", &n);
	while (n / a != 0) {
		left = n / (a * 10);
		now = n / a % 10;
		right = n%a;
		if (now == 0) ans += left * a;
		else if (now == 1) ans += left * a + right + 1;
		else ans += (left + 1)*a;
		a *= 10;
	}
	printf("%d\n", ans);
	return 0;
}

© 著作权归作者所有

共有 人打赏支持
粉丝 21
博文 954
码字总数 657923
作品 0
西安
PAT (Advanced Level) 1004. Counting Leaves (30) BFS

题目链接 Counting Leaves Time limit:1 seconds Memory limit:256 megabytes Problem Description A family hierarchy is usually presented by a pedigree tree. Your job is to count tho......

xp731574722
03/09
0
0
分布式系统阅读清单

原文链接 https://dancres.github.io/Pages/ A Distributed Systems Reading ListIntroductionI often argue that the toughest thing about distributed systems is changing the way you t......

HappyBoyLi
2017/12/14
0
0
MySQL数据库 行超限

Row size too large. The maximum row size for the used table type, not counting BLOBs, is 65535. This includes storage overhead, check the manual. You have to change some columns......

青春掌柜
2017/06/19
0
0
华为 vpn 配置 实现

实验名成:华为vpn配置实现 实验拓扑图: 3. 实验目的 :1. 使内网 172.16.10.0 配置vpn虚拟专用网可以访问AR3内网 web 服务器 2. 使内网 172.16.20.0 网段,配置动态pat可以上外网 4. 地址规...

kf690621683
02/08
0
0
位运算技巧

Compute the sign of an integer int v; // we want to find the sign of vint sign; // the result goes here // CHAR_BIT is the number of bits per byte (normally 8).sign = -(v < 0); ......

-_-struggle
2016/11/10
9
0
asa 动态地址的转化,以及,端口映射

asa 动态地址的转化,以及端口的映射 实验拓扑图 4. 实验目的 : 1. 将内网 10.1.1.0 ,10.2.2.0 网段 通过pat转换 能够访问外网 ftp服务器 2. 将内网dmaz区的web,ftp分别做映射,使从外网可...

kf690621683
01/31
0
0
ASA防火墙Dynamic NAT配置

说明: OUTSIDE模拟外网:e/0接口IP:200.200.200.200/24,lo0:8.8.8.8/32,lo10:114.114.114.114/32 INSIDE模拟内网:vlan 10:10.10.10.1/24,vlan 20:10.10.20.1/24,vlan 30:10.10.30.1/......

TTTommyyy
06/27
0
0
30.3. cpu

[root@F5:Active] config # cat /proc/cpuinfo processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 15 model name : Intel(R) Xeon(R) CPU X3220 @ 2.40GHz stepping : 11 cpu ......

玄学酱
01/08
0
0
phpstorm的java环境jdk太耗资源

phpstorm的java环境jdk太耗资源,安装了个phpstorm,以为耗资源比netbeans少,结果发现java的进程太耗cpu了,一般都彪到100%~300%,电脑被搞死了,还怎么工作啊,直接没法敲代码了。求高手赐教...

koko-hao
2014/06/09
3K
5
Top K Frequent Items Algorithm

Top K Frequent Items Algorithm Zhipeng Jiang2017-11-141 阅读 Top K frequent elements is a classic interview question that requires a basic understanding of HashMap and Heap. In ......

Zhipeng Jiang
2017/11/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

实现异步有哪些方法

有哪些方法可以实现异步呢? 方式一:java 线程池 示例: @Test public final void test_ThreadPool() throws InterruptedException { ScheduledThreadPoolExecutor scheduledThre......

黄威
今天
0
0
linux服务器修改mtu值优化cpu

一、jumbo frames 相关 1、什么是jumbo frames Jumbo frames 是指比标准Ethernet Frames长的frame,即比1518/1522 bit大的frames,Jumbo frame的大小是每个设备厂商规定的,不属于IEEE标准;...

六库科技
今天
0
0
牛客网刷题

1. 二维数组中的查找(难度:易) 题目描述 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入...

大不了敲一辈子代码
今天
0
0
linux系统的任务计划、服务管理

linux任务计划cron 在linux下,有时候要在我们不在的时候执行一项命令,或启动一个脚本,可以使用任务计划cron功能。 任务计划要用crontab命令完成 选项: -u 指定某个用户,不加-u表示当前用...

黄昏残影
昨天
0
0
设计模式:单例模式

单例模式的定义是确保某个类在任何情况下都只有一个实例,并且需要提供一个全局的访问点供调用者访问该实例的一种模式。 实现以上模式基于以下必须遵守的两点: 1.构造方法私有化 2.提供一个...

人觉非常君
昨天
0
0
《Linux Perf Master》Edition 0.4 发布

在线阅读:https://riboseyim.gitbook.io/perf 在线阅读:https://www.gitbook.com/book/riboseyim/linux-perf-master/details 百度网盘【pdf、mobi、ePub】:https://pan.baidu.com/s/1C20T......

RiboseYim
昨天
1
0
conda 换源

https://mirrors.tuna.tsinghua.edu.cn/help/anaconda/ conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/free/conda config --add channels https://mir......

阿豪boy
昨天
1
0
Confluence 6 安装补丁类文件

Atlassian 支持或者 Atlassian 缺陷修复小组可能针对有一些关键问题会提供补丁来解决这些问题,但是这些问题还没有放到下一个更新版本中。这些问题将会使用 Class 类文件同时在官方 Jira bug...

honeymose
昨天
0
0
非常实用的IDEA插件之总结

1、Alibaba Java Coding Guidelines 经过247天的持续研发,阿里巴巴于10月14日在杭州云栖大会上,正式发布众所期待的《阿里巴巴Java开发规约》扫描插件!该插件由阿里巴巴P3C项目组研发。P3C...

Gibbons
昨天
1
0
Tomcat介绍,安装jdk,安装tomcat,配置Tomcat监听80端口

Tomcat介绍 Tomcat是Apache软件基金会(Apache Software Foundation)的Jakarta项目中的一个核心项目,由Apache、Sun和其他一些公司及个人共同开发而成。 java程序写的网站用tomcat+jdk来运行...

TaoXu
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部