专栏文章

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

WWallacewwz
P1980题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqkm2ki
此快照首次捕获于
2025/12/04 06:20
3 个月前
此快照最后确认于
2025/12/04 06:20
3 个月前
查看原文

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

题目大意

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

解题思路

本题的目标是计算数字 xx 出现在 11 到 nn 区间内所有整数中的总次数。可以通过以下步骤来解决：
  1. 逐一检查每个数字：对于每一个数字 ii 从 11 到 nn，我们将其转换为字符串，并检查每个字符是否等于给定的数字 xx。如果是，则计数加一。
  2. 使用整数取余和整除：为了高效计算每个数字中数字 xx 的出现次数，我们可以通过取余和整除的方式逐个获取数字的各位数字，并判断是否等于 xx。这可以避免字符串转换带来的额外开销。
  3. 累加结果：在遍历完所有数字后，我们将得到数字 xx 出现的总次数。

复杂度分析

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

代码实现

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...