题解

题目解析

• 输入输出：第一行输入正整数 $n$（范围上限），第二行输入目标数字 $k$（$1 \leq k \leq 9$）；输出 $k$ 在整数 $1$ 到 $n$ 的所有数位中出现的总次数。
• 数据范围：$1 \leq n \leq 1000$，数据规模极小，允许逐位检查每个数字。
• 复杂度要求：时间复杂度 $O(n \cdot \log_{10}n)$（最多遍历 $1000 \times 4$ 个数位），空间复杂度 $O(1)$ 或 $O(\log n)$（字符串临时空间）。
• 算法知识点：模拟、枚举、数位统计、字符串转换

思路解析

1. 问题分解：将“统计区间 $[1, n]$”分解为对每个整数单独统计并累加。即遍历 $i \in [1, n]$，计算数字 $i$ 中包含多少个 $k$，求和得答案。
2. 数位提取（字符串法）：对于单个整数 $x$，利用 to_string(x) 将其转换为字符串，遍历每个字符：
   • 通过 s[i] - '0' 将字符转换为对应的数值；
   • 若等于 $k$，则计数器加一。
     注：也可使用数学方法（x % 10 取个位后 x /= 10），但字符串法代码更简洁。
3. 累加输出：主函数中维护累加器 ans，调用统计函数并输出最终结果。

完整代码

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

// 统计数字x中目标数字k出现的次数
int count(int x, int k) {
    int cnt = 0;
    // 将整数转为字符串，便于逐位检查
    string s = to_string(x);
    for (int i = 0; i < s.size(); i++) {
        // 字符转数字：'0'的ASCII码是48，'5'-'0'=5
        int num = s[i] - '0';
        if (num == k) cnt++;
    }
    return cnt;
}

int main() {
    int n, k;
    cin >> n >> k;  // 读入范围n和目标数字k
    
    int ans = 0;
    // 遍历1到n的每个整数
    for (int i = 1; i <= n; i++) {
        ans += count(i, k);  // 累加每个数中k的出现次数
    }
    cout << ans << endl;

    return 0;
}