蓝桥杯好数问题解析与C++实现

1. 题目背景与需求分析

今天要讨论的是蓝桥杯2024年省赛B组的一道编程题——"好数"问题。这道题看似简单，但考察了选手对数字位操作的基本功和优化意识。我们先明确题目要求：

题目定义了一个特殊数字概念"好数"：从低位到高位（个位为第1位），奇数位上的数字必须是奇数，偶数位上的数字必须是偶数。例如：

• 1234：第1位(个位)4(偶)×，不符合
• 1236：第1位6(偶)×，第2位3(奇)×
• 1357：第1位7(奇)√，第2位5(奇)×
• 2468：第1位8(偶)×
• 1230：第1位0(偶)×

题目要求统计1到N之间所有满足条件的"好数"数量，其中N的最大值为10^7。这个数据范围意味着我们需要一个时间复杂度为O(N)或更优的算法。

2. 算法设计与实现

2.1 基础解法思路

最直观的解法是遍历1到N的每个数字，逐个检查是否符合"好数"的定义。检查一个数字是否为好数的过程可以分为以下步骤：

1. 初始化位数计数器pos=1（从个位开始）
2. 循环取出数字的每一位：
   • 当前位数字digit = i % 10
   • 如果pos是奇数位且digit是偶数 → 不是好数
   • 如果pos是偶数位且digit是奇数 → 不是好数
   • i /= 10（去掉已检查的最低位）
   • pos++（处理下一位）
3. 如果所有位都通过检查，则是好数

2.2 C++实现详解

cpp复制#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool isGood(ll i) {
    int pos = 1; // 位数计数器，从个位(第1位)开始
    while(i > 0) {
        int digit = i % 10; // 取出当前最低位
        
        // 检查奇数位和偶数位的数字是否符合要求
        if(pos % 2 != 0) { // 奇数位(1,3,5...)
            if(digit % 2 == 0) return false;
        } else { // 偶数位(2,4,6...)
            if(di