P10424【蓝桥杯 2024 省 B】好数

1. 解题思路

题目要求统计 1 到 N 之间有多少个“好数”。

所谓好数，就是一个整数从低位到高位，满足以下条件：

  • 奇数位（个位、百位、万位……）上的数字必须是奇数。
  • 偶数位（十位、千位、十万位……）上的数字必须是偶数。

注意，数位是从个位开始编号的，个位是第 1 位，十位是第 2 位，以此类推。

例如，123 就是一个好数：

纯文本
数字：   1   2   3
数位：   3   2   1
要求：  奇  偶  奇
结果：   ✓   ✓   ✓

三个数位都符合要求，因此 123 是好数。

这道题可以直接使用枚举的方法：从 1 遍历到 N，逐个检查每个整数的所有数位。如果全部满足条件，就将答案加一；只要有一位不符合要求，就直接跳过当前数字。

实现时，关键在于如何从个位开始依次获取每一位数字。

下面分别使用 C++ 和 Python 的两种写法来实现。

2. C++：字符串反转

C++ 版本采用字符串处理的方法。

首先，使用 to_string() 将整数转换成字符串，再通过 reverse() 将字符串反转。

这样一来，原本位于最后的个位数字就被放到了字符串开头，我们可以直接从左往右遍历。

需要注意数组下标与数位编号的区别：

  • 下标 j = 0，对应原数的第 1 位（个位）。
  • 下标 j = 1，对应原数的第 2 位（十位）。
  • 下标 j = 2，对应原数的第 3 位（百位）。

因此，当 j 为偶数时，实际上对应的是题目中的奇数位，需要检查当前数字是否为奇数；反之，则需要检查是否为偶数。

代码中使用 flag 记录当前整数是否符合要求。一旦发现某一位不合法，就将 flag 设为 0，并通过 break 提前结束检查。

C++ 代码：

C++
#include<iostream>
using namespace std;
#include<string> 
#include<algorithm> 
int main()
{
    int n=0;
    cin>>n;
    int count=0;
    for(int i=1;i<=n;i++)
    {
        // 将数字转成字符串,然后反转. 
        string s=to_string(i);
        reverse(s.begin(),s.end());
        bool flag=1;
        //反转后的字符串,最高位就是原本的奇数位了,然后往后遍历. 
        for(int j=0;j<s.size();j++)
        {
            //如果j能被2整除,比如0,那其实是奇数位. 
            if(j%2==0)
            {
                //奇数位如果被2整除就不符合条件. 
                if((s[j]-'0')%2==0)
                {
                    flag=0;
                    break; 
                }
            }else{
                //偶数位不能被2整除就不符合条件. 
                if((s[j]-'0')%2!=0)
                {
                    flag=0;
                    break; 
                }
            }
        }
        //如果所有数位都符合条件,flag依然是1,然后统计次数加一次. 
        if(flag)count++;
    }
    //最后打印一下 
    cout<<count<<endl;
}

这里的 s[j] - '0' 是将数字字符转换成对应的整数，方便使用 % 2 判断奇偶性。

3. Python：取模与整除

Python 版本没有使用字符串，而是通过取模和整除直接处理整数的每一位。

对于一个正整数 x：

  • x % 10：获取当前的个位数字。
  • x //= 10：去掉个位数字，让原来的十位变成新的个位。

不断重复这两个操作，就可以按照从低位到高位的顺序检查整个整数。

例如，对于 123：

纯文本
x = 123 → x % 10 = 3 → 第 1 位，奇数 ✓
x = 12  → x % 10 = 2 → 第 2 位，偶数 ✓
x = 1   → x % 10 = 1 → 第 3 位，奇数 ✓
x = 0   → 检查结束

代码中使用 cnt 记录当前检查的是第几位。

判断数位编号是否为奇数时，我使用了 cnt & 1。这是一个按位与操作：对于非负整数，如果最低二进制位为 1，说明它是奇数；否则就是偶数。

最后，将判断逻辑封装为 check() 函数：

  • 如果某一位不符合条件，直接返回 False。
  • 如果所有数位都检查完毕，没有发现问题，就返回 True。

Python 代码：

Python
def check(x):
    # cnt标志是奇数位还是偶数位,
    cnt=1
    # x不为0就一直对10取模求最后一位,然后整除10去掉最后1位
    while x!=0:
        t=x%10
        x//=10
        if cnt&1:
            # 如果cnt是奇数,t是偶数就不符合条件,直接返回False
            if t%2==0:
                return False
        else:
            # 如果cnt是偶数,t是奇数就不符合条件,直接返回False
            if t%2==1:
                return False
        cnt+=1
    return True
        
n=int(input())
count=0
for i in range(1,n+1):
    if check(i):
        count+=1
print(count)

这两种写法虽然处理数位的方式不同，但判断逻辑是一样的：从个位开始，按照数位编号依次检查数字的奇偶性，全部符合要求才计入答案。

4. 复杂度与运行时间

假设输入的上限为 N。

外层循环需要枚举 1 到 N 的所有整数，而每个整数最多需要检查 O(log₁₀ N) 个数位。

因此，整体时间复杂度为：

O(Nlog⁡10N)O(N\log_{10}N)

Python 版本只需要少量辅助变量，额外空间复杂度为 O(1)；C++ 版本需要将整数转换为字符串，因此还需要 O(log N) 的额外空间。

不过，这道题的 N 最大可以达到 10710^7。虽然每个整数最多只有 8 位，但枚举次数仍然很多。

我当时提交 Python 版本时，需要使用 PyPy3 才能通过。对于这种包含大量循环和整数运算的题目，不同 Python 解释器以及评测环境的执行效率，确实可能影响最终的运行时间。

这道题的解法并不复杂，主要练习的是枚举和数位处理。相比字符串反转，通过取模和整除逐位检查整数，也是一种值得掌握的基础写法。

谢谢你读到这里。 ✧

聊两句

评论审核后显示

有疑问、补充，或者想交流一下，都可以写在这里。

评论区将在滚动到这里时加载。