[NOIP 2013 普及组] 计数问题

知识点

枚举、数位统计

解题思路

枚举1到n，将每个整数转为十进制字符串，统计其中等于数字x对应字符的位置数。

正确性说明

1到n每个整数恰访问一次，其中每个十进制数位恰检查一次；每次匹配贡献1，因而没有遗漏或重复。

易错点

统计出现次数而非包含x的整数个数；x=0时也应按正常十进制表示统计，不补前导零。

复杂度

时间O(n log(n+1))，额外空间O(log(n+1))。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,x;cin>>n>>x;int ans=0;
    for(int i=1;i<=n;++i) for(char c:to_string(i)) if(c==char('0'+x)) ++ans;
    cout<<ans<<'\n';
}