Home PAT 1049 Counting Ones
Post
Cancel

PAT 1049 Counting Ones

Link

题意: 给定一个数 n, 求出 1~n 这 n 个十进制数中 1 出现的次数. 例如 11 中 1 出现了 2 次, 10 中出现了 1 次.

思路: 对于 n, 假设它写成十进制有 m 位, 表示为:

$a_m a_{m-1} a_{m-2} \dots a_2 a_1$

其中 \(n=a_m*10^{m-1}+a_{m-1}*10^{m-2}+\dots +a_2*10+a_1\).

那么就对这 m 位从低到高遍历一遍, 每次将这 m 个数按照当前位划分为三组: left, cur, right

第 1 次:

$a_ma_{m-1}\dots a_{2},a_{1},0$

第 2 次:

$a_ma_{m-1}\dots a_{3},a_{2},a_{1}$

第 3 次:

$a_ma_{m-1}\dots a_{4},a_{3},a_{2}a_{1}$

……

第 m 次:

$a_m,a_{m-1},a_{m-2}\dots a_{2}a_{1}$

这样划分的作用很明显. 因为当前位 cur 的值很重要:

例如 21031 这个数, 当前位是 0, 那么 left=21, cur=0, right=31.

此时, 我们想要找出不超过 n 的数中 cur 位 (即从低到高的第 3 位, 百位) 为 1 的数的个数.

但是现在 cur 位为 0, 相当于是要将 cur 位增大, 那么只好借位了 —— 那就是让 left 变小. left 本来是 21, 那么我们就取 left 在 [0,20] 这个闭区间内的值, 这样 cur 位就可以取 [0,9] 中的任意值了! 但是我们只需要 1, 这样我们就可以计算出 cur 位为 1 的数的个数.

left 确定了, 那么 right 该怎么取值呢?

如果 left<21, 那么 right 可以取 [0,99] 中的任意数; 如果 left==21, 那么 right 只能取 [0,31] 中的数, 而且此时 cur 必须为 0. 但是现在我们考虑 cur==1 的情况, 因此 right可以取 [0,99] 中的任意数. 综上, cur 位为 1 的不大于 n 的数为 (20-0+1)*(99-0+1)=2100.

在遍历每一位的过程中, 我们设置了 a 来表示当前位处于整个数的什么位置 —— 如果当前位是个位, a 就是 1; 如果当前位是十位, a 就是10…以此类推. 因此, right 部分的取值范围是 [0,a-1] 这个闭区间, 总个数是 a-1-0+1=a.

刚才是 cur==0 的情况. 如果 cur==1, 那么当 left 取 [0,left-1] 时, right 可以取 [0,a-1]; 当 left 取值就是 left 时, right 只能取 [0,right], 即 right+1 个数.

如果 cur>2, 那么 left 取 [0,left], right 取 [0,a-1].

由于是要求所有 1 的个数, 因此不需要担心这个数在这种计算方法中重复的问题 (实际上, 一个数中有几个 1, 这个数就要出现几次). 如果是计算所有包含 1 的数的个数, 就要考虑重复的问题了.

对于任意整数 n, n % 1 = 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int main() {
    int n,a=1,left,cur,right,ans=0;
    scanf("%d",&n);
    while(n/a){
        left=n/(a*10),cur=(n/a)%10,right=n%a;
        if(cur==0) ans+=left*a;
        else if(cur==1) ans+=left*a+right+1;
        else ans+=(left+1)*a;
        a*=10;
    }
    printf("%d\n",ans);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.