♐ CSP_J 组真题
2013年
1. 计数问题

线上OJ:

一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1961 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/455/ (opens in a new tab)
洛谷:https://www.luogu.com.cn/problem/P1980 (opens in a new tab)

核心思想:

本来想找规律,后来发现本题的数据范围不大,n为10610^6,即使每一位都判断一次,最坏的情况下时间复杂度也仅为O(7106)O(7*10^6),故本题可以考虑直接枚举,不需要去找数字上的规律了。

题解代码:

解法、(枚举):
#include <bits/stdc++.h>
using namespace std;
 
int n, x, ans=0;
 
int main()
{
    cin >> n >> x;
    for(int i = 1; i <= n; i++)
    {
        int tmp = i;  // 这里需要用tmp代替i,因为i要++,i不能变
        while(tmp)  
        {
            if((tmp % 10) == x)  ans++;  // 如果最后一位是x,则ans++
            tmp = tmp / 10;    // 去除个位数字
        }
    }
    cout << ans << endl;
    return 0;
}
 

备注:如果只看100以内,我们会发现 1 ~ 9 的数字: 每满100出现20次。0 比较特殊要单独计算

  0   1   2   3   4   5   6   7   8   9
 10  11  12  13  14  15  16  17  18  19
 20  21  22  23  24  25  26  27  28  29
...
 90  91  92  93  94  95  96  97  98  99
---------------------------------------
100 101 102 103 104 105 106 107 108 109
110 111 112 113 114 115 116 117 118 119
120 121 122 123 124 125 126 127 128 129
...
190 191 192 193 194 195 196 197 198 199