【例36.2】 计数问题

解题思路

枚举1～n，逐位分离十进制数字，等于x就计数。同一个数可能多次贡献，例如11对数字1贡献2次。

正确性说明

按上述推导执行：每次仅处理当前输入或当前步骤，并把它对答案的贡献计入对应状态。所有需要处理的情况均被覆盖，结束时保存的量就是题目所求。

易错点

不计不存在的前导零。

复杂度

时间O(n log n)，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, x;
    cin >> n >> x;
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        for (int t = i; t; t /= 10)
            if (t % 10 == x)
                ans++;
    cout << ans << "\n";
    return 0;
}