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

kuaiCreator · 2025-01-07 13:32:30 · 题解

解题思路

对于十进制数，取模 10 可获得当前数的个位，整除 10 可去掉当前数的个位，要获取当前数的每一位可以循环取个位，去个位，直到这个数被拆分为 0。因此观察数据范围后只需要枚举区间 [1,n] 内的所有数进行拆分并统计 x 的个数即可，时间复杂度为 O(n\log n)。

如果数据范围很大，这样做会超时，可以学习数位动态规划解决本题。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main() {
    int m, x, ans = 0;
    cin >> m >> x;
    for (int i = 1; i <= m; i++) {  //枚举区间[1,m]的数
        int n = i;  //避免i变成0造成死循环备份i的值
        while (n) {
            if (n % 10 == x) ans++; //个位为x累加答案
            n /= 10;
        }
    }
    cout << ans;
    return 0;
}