G2012 [GESP202406 二级] 计数 题解

知识点：数字处理、嵌套循环、计数。

解题思路

从1到n逐个拆分十进制数位，用%10取末位、/10删末位，遇到k就累计一次。

为什么正确

每个整数的每一位被访问一次，得到k在全部数中出现的总次数。

易错点

同一整数中k出现多次要多次计数；输入范围从1开始。

复杂度

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

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k,ans=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++)for(int t=i;t;t/=10)ans+=t%10==k;
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用6个自行生成的测试点。