【PAT（甲级）】1049 Counting Ones（与位数以及位数上的数字有关）

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”的个数，可以统计每个位上“1”出现的次数。

比如说题目中的“12”：

个位数上的“1”{1，11}出现两次；

十位数上的“1”{10，11，12}出现三次；

所以总计五次。

而每个位上出现“1”的次数，与这个数在这位上的数字有关。

那么根据规律我们可以得出（如果前面没有数字则默认为0）：

1.         该位上的数字小于1，则它前面的数字，即为“1”出现的次数。例如：“21340”中个位为“0”小于1，则个位上“1”出现的次数为2134次；

2.        若该位上的数字等于1，则（它前面的数字乘以该位位数+该位后面的数字+1）即为该位上“1”出现的次数。例如：“21340”中千位上为“1”，则千位上“1”出现的次数为（2*1000+340+1）次。

3.        若该位上的数字大于1，则（该位前面的数+1）*该位位数，即为该位上“1”出现的次数。例如：“21340”中十位上为“4”，则十位上“1”出现的次数为（213+1）*10；百位上为“3”则百位“1”出现的次数为（21+1）*100.

代码：

#include
using namespace std;
 
int turn_int(string a){
	return atoi(a.c_str());
}
int main(){
	long long int N;
	cin>>N;
	int sum = 0;
	int left,right,now,tip = 1;
	while(N/tip!=0){
		left = N / (tip*10);
		right = N % tip;
		now = N / tip % 10;
		
		if(now == 0) sum += left*tip;
		else if(now == 1) sum += left*tip + right + 1;
		else sum += (left+1) * tip;
		
		tip *= 10;
	}
	cout<
	return 0;
}