专栏文章

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

kkuaiCreator
P1980题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqklzjd
此快照首次捕获于
2025/12/04 06:20
3 个月前
此快照最后确认于
2025/12/04 06:20
3 个月前
查看原文

解题思路

对于十进制数，取模 1010 可获得当前数的个位，整除 1010 可去掉当前数的个位，要获取当前数的每一位可以循环取个位，去个位，直到这个数被拆分为 00。因此观察数据范围后只需要枚举区间 [1,n][1,n] 内的所有数进行拆分并统计 xx 的个数即可，时间复杂度为 O(nlog⁡n)O(n\log n)。
如果数据范围很大，这样做会超时，可以学习数位动态规划解决本题。

代码实现

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...