题解：P1980 [NOIP2013 普及组] 计数问题

· · 题解

[NOIP2013 普及组] 计数问题 题解

题目大意

给定一个整数区间 1 到 n，我们需要计算数字 x（0 \leq x \leq 9）在区间内所有整数中共出现了多少次。例如，在区间 [1, 11] 中，数字 1 出现了 4 次，分别出现在 1, 10, 11 中。

解题思路

本题的目标是计算数字 x 出现在 1 到 n 区间内所有整数中的总次数。可以通过以下步骤来解决：

  1. 逐一检查每个数字：对于每一个数字 i 从 1 到 n，我们将其转换为字符串，并检查每个字符是否等于给定的数字 x。如果是，则计数加一。

  2. 使用整数取余和整除：为了高效计算每个数字中数字 x 的出现次数，我们可以通过取余和整除的方式逐个获取数字的各位数字，并判断是否等于 x。这可以避免字符串转换带来的额外开销。

  3. 累加结果：在遍历完所有数字后，我们将得到数字 x 出现的总次数。

复杂度分析

对于 n 最大为 10^6 的情况，这种方法是可行的，且可以在合理时间内完成。

代码实现


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

int n, k, ans;

// 计算数字num中数字k的出现次数
void calc(int num)
{
    while(num)
    {
        if((num % 10) == k) ans++;  // 如果当前位等于k，则计数加一
        num /= 10;  // 去掉当前位
    }
}

signed main()
{
    cin >> n >> k;  // 输入n和k
    for(int i = 1; i <= n; i++)  // 遍历区间[1, n]
        calc(i);  // 计算每个数中数字k出现的次数
    cout << ans << '\n';  // 输出结果
    return 0;
}