统计次数
给定两个正整数 \(n\) 和 \(k\)，求从 \(1\) 到 \(n\) 这 \(n\) 个正整数的十进制表示中 \(k\) 出现的次数。
输入格式
共一行，包含两个整数 \(n\) 和 \(k\)。
输出格式
输出一个整数，表示答案。
数据范围
\(1≤n≤10^6,\)
\(1≤k≤9\)
输入样例：
12 1
输出样例：
5
样例解释
从 \(1\) 到 \(12\) 这些整数中包含 \(1\) 的数字有 \(1,10,11,12，\)一共出现了 \(5\) 次 \(1\)。
暴力 \(O(nlogn)\)(174 ms)
具体实现
从 1 遍历到 n，分别统计每个数中 k 出现的次数。
不断取 x 的末尾，判断它是否为 k，再把 x 除以 10（舍弃末位）。
点击查看代码
#include<iostream>
using namespace std;
typedef long long LL;
int n,k;
LL ans;
int main(){
cin >> n >> k;
for(int i = 1; i <= n; i ++ ){
int t = i;
while(t){
if(t % 10 == k)ans ++;
t /= 10;
}
}
cout << ans;
}
数位DP \(O(n)\)(62 ms)
\(f[i]\) 表示 \(i\) 中含有几个 \(k\)。观察可得到转移方程 \(fi=f⌊i/10⌋+ (i \% 10 == k)\)，其中 \(bj\) 为 \(j\) 是否等于 \(k（0≤j≤9）\)。如此递推即可
点击查看代码
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n,k;
int f[N];
LL ans;
int main(){
cin >> n >> k;
for(int i = 1; i <= n; i ++ )f[i] = f[i / 10] + (i % 10 == k),ans += f[i];
cout << ans;
}