1049. Counting Ones.md

pat 甲级 1049 Counting Ones

题意概述

给定任何正整数 N，您应该以从 1 到 N 的整数的十进制形式计算 1 的总数。例如，假设 N 为 12，则数字 1、10、11、12 共有 5 个 1。

输入输出格式

输入给出正整数 N。

在一行中打印数字 1 出现的次数。

算法设计

显然暴力枚举的方法是不可取的，我们需要寻找其中的规律，本题中可以分别计算出每一位的1出现的个数再进行加和。本博客中以数字N=345、N=305、N=315为例，寻找十位数字上是1的数字个数。将数字分成 3 部分：百位、十位、各位。 显然，从1~345这 345 个数中，百位数字可以出现0、1、2、3四种，每种百位数字都可以跟一个数字为1的十位，而每种十位数字可以跟0~9这十种数字，所以从1~345这 345 个数中，十位数字为1的数共有$(3+1)×10=40$个，故十位上的1共出现 40 次。 当N=305时，百位数字依然可以出现0、1、2、3四种，但要注意，百位数字为3时，后面不能再跟数字为1的十位，因为这样的数字已经大于 305 了，所以从1~305这 305 个数中，十位数字为1的数共有$3×10=30$个，故十位上的1共出现 30 次。 当N=315时，百位数字依然可以出现0、1、2、3四种，此时要注意，百位数字为3时，后面可以再跟数字为1的十位，但这样的数字个位上只能出现0~5这 6 个数，即310、311、312、313、314、315，其他数字都会大于 315，所以从1~315这 315 个数中，十位数字为1的数共有$3×10+(5+1)=36$个，故十位上的1共出现 36 次。

综上，对于任意一个数字 N，当要判断从右向左数第i位上1出现的次数num时，可以将这个数字分成三部分，分别用left、current、right表示，即left=数字N在i位左侧的数字、current=数字N在第i位的数字、right=数字N在i位右侧的数字。例如数字N=123456，判断从右向左第 2 位也就是百位上，即数字4所在位置1出现的次数时，left=123、current=4、right=56。此时分三种情况进行计算：

1. $current=0$：$num=left×10^i$
2. $current=1$：$num=left×10^i+(right+1)$
3. $current>1$：$num=left×10^i+10^i$

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, ans = 0;
    cin >> ni;
    gg left = ni / 10, right = 0, current = ni % 10;
    for (gg i = 1; right != ni; i *= 10) {
        ans += left * i + (current == 0 ? 0 : current == 1 ? (right + 1) : i);
        right += current * i;
        current = left % 10;
        left /= 10;
    }
    cout << ans;
    return 0;
}