PAT甲级1049 Counting Ones (30 分)--参考于柳神

1049 Counting Ones (30 分)
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 (≤2^30).

Output Specification:
For each test case, print the number of 1’s in one line.

Sample Input:

12

Sample Output:

5

PAT甲级1049 Counting Ones (30 分)--参考于柳神
虽然上图与下面的解释不能完全对号入座

这是一个组合的问题:好比A={x|x=i,i=0,1,2...,n},B={y|y=i,i=0,1,2...,m},对于Point(x,y)有n*m种可能。
now=0时,ans+=left*a{左边任意取一个0~(left-1)的数,在now位上都可以取1(如果左边取left的话,该数就会大于120),
    				a由now位所在位置产生:如果now位在十位的话,右边就可以取0~9这十个数,
    				好比挑选一对男女去挑拉丁舞的问题,男生有n人,女生有m人,总共有n*m种组合。}
now=1时,ans+=left*a+(right+1){在now=0的基础上加多了right+1,为什么呢?由于左边取到left时,now位上取1不会越界。
    					为什么可以多加right+1呢?当左边取到left时,now位上可以取1,右边可以取0~right个数,也不会发生越界现象。
    					就好比在中午吃饭时有m个不同的午饭可以选择,如果一次只能选一个的话,那就有m种可能。
    					}
now>=2时,ans+=(left+1)*a{在now位上取1的基础上,左边可以取0~left这(left+1)个数,
    										右边可以取0~a-1这a个数。因此就是一个n*m的组合。
    					}

代码

#include<iostream>
using namespace std;

int main() {
	int left, right, now, a = 1, ans = 0, n;
	cin >> n;
	while (n / a) {
		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 if (now >= 2)ans += (left + 1) * a;
		a *= 10;
	}
	cout << ans << endl;
	return 0;
}

参考于下

https://blog.csdn.net/liuchuo/article/details/52264944

上一篇:PAT-A1029 Median


下一篇:PAT 甲级 1001 A+B Format