返回题解分享
讨论 / 题解分享/ 帖子详情

好数(编程题) - 题解

朴素的筛法,考场写的没有做优化

#include <iostream>
using namespace std;

const int N = 1e7 + 10;
bool st[N];

void get_good_nums(int n){
	int t = n, len = 0;
	while(t){
		len ++;
		t /= 10;
	}
	// 枚举位数
	int b = 1;
	bool flag = true; // 从奇数开始 
	for(int i = 1; i <= len; ++ i){
		for(int j = b; j <= n; ++ j){
			if(flag){
				if((j / b % 10) % 2 == 0) st[j] = true;
			}else{
				if((j / b % 10) % 2 != 0) st[j] = true;
			}
		}
		flag = !flag;
		b *= 10;
	} 
}
int main(){
	int n;
	cin >> n;
	get_good_nums(n);
	
	int ans = 0;
	for(int i = 1; i <= n; ++ i)
//		if(!st[i]) cout << i << " ";
		if(!st[i]) ans ++;
	cout << ans;
	return 0;
}
1 回复 0 转发 0 喜欢 11 阅读
回复 (1)
默认 最新
露米 2026/3/1
在考场那种紧张的情况下,能迅速理清思路并实现出来已经很棒了。

用标记数组的思路很清晰,这种“先标记再统计”的方式在处理这类题目时确实很稳妥。如果之后想尝试减少一些重复计算,可以考虑在一次遍历中直接判断每个数字是否符合条件。

慢慢优化就好,不着急的。如果有新的想法,也欢迎继续分享出来呀 🙂
另外,我注意到你在定义数组大小时特意加了 10 的缓冲区,这种细心的小习惯在考场上特别重要,能帮我们规避掉不少意外的边界风险。

期待你以后更多的分享,如果遇到其他有趣的题目,也可以再叫我一起讨论呀。
0