PAT (Advanced Level) Practice 1049 Counting Ones (30 分) 凌宸1642
题目描述：
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.
译：任务很简单：给定任何正整数 N，您应该计算从 1 到 N 的整数的十进制形式的 1 总数。例如，假设 N 为 12，则 1、10 中有五个 1， 11 和 12。
Input Specification (输入说明):
Each input file contains one test case which gives the positive N (≤230).
译：每个输入文件包含一个测试用例，它给出正 N(≤230)。
output Specification (输出说明):
For each test case, print the number of 1’s in one line.
译：对于每个测试用例，在一行中打印 1 的数量。
Sample Input (样例输入):
12
Sample Output (样例输出):
5
The Idea：
- 数学排列组合逻辑问题。
- 自己模拟的话，是肯定会超时的，根据算法笔记上的解法，会发现其实代码很简单，但是很难想
- 计算
n 的每一位数产生的1的数量 ， 每次根据当前位置的数字，将 n 分为部分，left 表示当前数字左边所有高位组成的数字，right 表示当前数字右边所有高位组成的数字 , now 表示当前数字：
- 如果
now == 0 ，我们不妨取 当前位为 1 ，然后左边的取值范围为 [0 , left - 1] 右边数的取值范围为 [0 , a - 1], 利用排列组合的乘法原理可知，当前数字产生 1 的个数为 left * a ； - 如果
now == 1 ，就存在两种情况了，一种和 now == 0时一致，另一种就是左边的取值为 left 右边数的取值范围为 [0 , right], 利用排列组合乘法原理和加法原理可知，当前数字产生 1 的个数为 left * a + right + 1 ； - 最后如果
now > 1 ，取当前位为 1 ,然后左边的取值范围为 [0 , left] 右边数的取值范围为 [0 , a - 1], 利用排列组合的乘法原理可知，当前数字产生 1 的个数为 (left + 1) * a 。
The Codes:
#include<bits/stdc++.h>
using namespace std ;
int main(){
int n , left , right , now , a = 1 , ans = 0 ;
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 ans += left * a + a ;
a *= 10 ;
}
cout << ans << endl ;
return 0 ;
}
|