3400. 统计次数
摘要
Title: 3400. 统计次数
Tag: 暴力、数位dp
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
3400. 统计次数
-
题意
给定两个正整数 n 和 k，求从 1 到 n 这 n 个正整数的十进制表示中 k 出现的次数。
-
思路
- 暴力
- 数位dp
-
代码
暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/*
* @Author: NEFU AB-IN
* @Date: 2023-01-01 12:16:23
* @FilePath: \Acwing\3400\3400.cpp
* @LastEditTime: 2023-01-01 12:18:20
*/
using namespace std;
typedef pair<int, int> PII;
// #undef N
// const int N = 1e5 + 10;
// #undef int
signed main()
{
IOS;
int n, k, ans = 0;
cin >> n >> k;
for (int i = 1; i <= n; ++i)
{
auto f = [&](int x) {
int res = 0;
while (x)
{
if (x % 10 == k)
res++;
x /= 10;
}
return res;
};
ans += f(i);
}
cout << ans;
return 0;
}
数位dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38/*
* @Author: NEFU AB-IN
* @Date: 2023-01-01 12:23:52
* @FilePath: \Acwing\3400.1\3400.1.cpp
* @LastEditTime: 2023-01-01 12:25:37
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
// #undef int
signed main()
{
IOS;
int n, k, ans = 0;
cin >> n >> k;
vector<int> dp(N);
for (int i = 1; i <= n; ++i)
{
dp[i] = dp[i / 10] + (i % 10 == k);
ans += dp[i];
}
cout << ans;
return 0;
}