PAT 解题报告 1049. Counting Ones (30)

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.

1049. Counting Ones 算法分析：

```dp[i+1] = dp[i]            // 1 到 9...9, i位数
+ 1 * 10 ^ (i-1)   // i+1位数, 首位的1出现的次数
+ 9 * dp[i]        // i+1位数, 非首位1出现的次数
```

```#include <iostream>
#include <cstring>
#include <cstdio>

#define REP(i,n) for(int i=0;i<(n);++i)

using namespace std;

int nones[12][2];

int main(void) {
nones[1][0] = 1;
int mul = 10;
for(int i=2; i<=9; ++i) {
nones[i][0] =   nones[i-1][0]
+ 1*mul
+ 9*nones[i-1][0] ;
mul *= 10;
}
int N;
scanf("%d", &N);
int cur_counts = 0;
int k = 0;
int num = N;
while(N) {
k++;
N /= 10;
}
if(1 == k) {
if(num)
printf("1\n");
else
printf("0\n");
return 0;
}

if(num%10)
cur_counts = 1;
else
cur_counts = 0;
mul = 1;
for(int i=2; i<=k; ++i) {
mul *= 10;
int hi = (num/mul)%10;
int low = num % mul;

if(hi > 1) {
cur_counts = hi * nones[i-1][0]
+ mul
+ cur_counts;
}
else if(hi == 1) {
cur_counts = hi * nones[i-1][0]
+ (low+1)
+ cur_counts;
}
else {
cur_counts = hi * nones[i-1][0]
+ 0
+ cur_counts;
}
}
printf("%d\n", cur_counts);
return 0;
}
```

1049. Counting Ones 注意点：

Written on January 19, 2014