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

niuniudundun · 2025-01-07 13:25:51 · 题解

题目大意

计算在 [1,n] 的所有整数中，数字 x(0\le x\le9) 共出现了多少次？

解法

标准的数位分解。

对于一个正整数 a，当 a \bmod 10 即可以取到最末尾的数值，\left \lfloor a {\div} 10 \right \rfloor 就是 a 删去最末尾的数值，重复过程就对 a 取出了每位的数值，这就是数位分解的基本思想。

如果发现正在数位分解的数字中数位有 x，则计数器就加一。

写成代码就是这样：

int count_(int a){
    int sum=0;//计数器
    while(a!=0){
        if(a%10==x){
            sum++;
        }
        a=a/10;
    }
    return sum;
}

因为要求 [1,n]，所以直接遍历 [1,n]。

代码：

复杂度：O(n \log_{10} n)。

#include<iostream>
using namespace std;
int n,x,ans=0;
int count_(int a){
    int sum=0;
    while(a!=0){
        if(a%10==x){
            sum++;
        }
        a=a/10;
    }
    return sum;
}
int main(){
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        ans+=count_(i);
    }
    cout<<ans<<endl;
    return 0;
}