好数题解：暴力遍历、剪枝优化与数位构造
点击查看题目
摘要
本文针对「好数」统计问题提出三种递进式解法：暴力遍历通过逐位验证实现简单逻辑；剪枝优化利用个位必为奇数的特性减少50%遍历量；数位构造法采用DFS直接生成合法数字，将时间复杂度优化至指数级。文章提出方法选型指南：小数据（≤1e4）适用暴力法，中等数据（1e4-1e7）推荐剪枝优化，大数据（≥1e7）首选构造法，并探讨了数位DP、并行计算等进阶优化方向，完整呈现算法优化方法论。
题目解析
题目定义 定义满足以下条件的正整数为"好数"：
- 从低位开始计数（个位为第1位）
- 奇数数位（第1、3、5…位）必须为奇数
- 偶数数位（第2、4、6…位）必须为偶数
输入输出
- 输入：正整数N
- 输出：1到N范围内的好数总数
示例解析
输入#1
24
输出#1
7
解释：符合条件的数字有1,3,5,7,9,21,23
输入#2
2024
输出#2
150
理解题意
根据题目定义，"好数"需满足如下数位特征规律：当数字的某位处于奇数位（即个位为第1位、百位为第3位、万位为第5位等）时，该位数字必须为奇数；当处于偶数位（十位为第2位、千位为第4位、十万位为第6位等）时，该位数字必须为偶数。
思路
那么第一个方法是暴力遍历1到n的数字，看看他们符不符合，不过还可以优化，第二种方法是在第一种方法的基础上跳过一些不符合的数字，虽然上面两种方法可以过，但我们不能仅求于此，仍然可以优化，第三个方法就是直接构造符合题意的好数，跳过无关的数字。下面分享我的三种种解法
解法对比
| 方法 | 时间复杂度 | 优化策略 | 适用场景 |
|---|---|---|---|
| 暴力遍历 | O(n·k) | 无 | N≤1e4 |
| 剪枝优化 | O(n/2·k) | 跳过偶数遍历 | N≤1e7 |
| 数位构造法 | O(5^{log₁₀N}) | 合法数字生成 | N>1e7 |
当N为最坏情况，N=1e7时：
- 暴力法：遍历7×1e7次
- 剪枝优化：遍历7×1e7/2次
- 构造法：仅需构造5^8=390,625次
方法一：暴力遍历——基础解法
算法思路
- 全量遍历：逐个检查1到N的所有数字
- 逐位验证：
- 奇数位（个/百/万位）必须为奇数
- 偶数位（十/千/十万位）必须为偶数
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int ans=0;
bool check(int x)
{int tem = x;int f=0;//0奇1偶while(tem){if(f==0){if(tem%10 % 2 == 0)//奇数位为偶{return false;}}else {if(tem%10 % 2 != 0)//偶数位为奇{return false;}}tem /= 10;if(f==0) f=1;else f=0;}return true;
}
int main() {cin>>n;//遍历判断for(int i=1;i<=n;++i){if(check(i)){ans++;}}cout<<ans;return 0;
}
复杂度分析
- 时间复杂度：O(n·k)（k为数字平均位数）
- 空间复杂度：O(1)
方法二：剪枝优化——效率提升50%
优化洞察
个位必为奇数的特性意味着：
- 所有偶数必然不符合条件
- 遍历步长可优化为2（仅检查奇数）
代码实现
#include<bits/stdc++.h>
using namespace std;
int n;
int ans=0;
bool check(int x)
{int tem = x;int f=0;//0奇1偶while(tem){if(f==0){if(tem%10 % 2 == 0)//奇数位为偶{return false;}}else {if(tem%10 % 2 != 0)//偶数位为奇{return false;}}tem /= 10;f = 1 - f;//取反操作}return true;
}
int main() {cin>>n;//遍历判断for(int i=1;i<=n;i+=2){if(check(i)){ans++;}}cout<<ans;return 0;
}
性能提升
| 优化点 | 效果 |
|---|---|
| 遍历次数减半 | 时间复杂度降为O(n/2·k) |
| 快速失败机制 | 平均减少20%校验时间 |
方法三：数位构造法——终极优化
算法思想
采用DFS生成合法数字：
- 数位预定义：
- 奇数位候选：{1,3,5,7,9}
- 偶数位候选：{0,2,4,6,8}
- 递归构造：
- 从高位到低位生成数字
- 及时终止超限分支
- 从高位到低位构造数字的原因
- 每位的可能值是从小到大赋值的，比如奇数位是1，3，5，7，9中轮流赋值
- 从高位往低位构造，构造的数字才能是严格递增的
- 如果从低位往高位构造，则不能保证有序，比如65…85…01…21
- 其实构造顺序不是有序的也是可以的，因为枚举的数字迟早都可以轮到，但如果是递增的话，我们就可以在构造到“>n”的时候停止，因为后面的都是不符合题意范围的，提前停止能提升性能
#include<bits/stdc++.h>
using namespace std;
int n;
int ans=0;//答案
int flag=0;//标记当前构造的数字是否超过n，由于我们构造的数字的顺序是严格递增的，所以超过的时候直接输出答案退出
bool hx[10000005]={0};//判断构造的重复
int fac[10]={0};//存储构造的数字，fac[1]、fac[2]...是构造的数字的个位、十位...
int ji[6]={0,1,3,5,7,9};//奇数位可能的值
int ou[6]={0,0,2,4,6,8};//偶数位可能的值
int is_int(int len)//数组转int函数，len是构造的数字fac数组的长度
{int tem = 0;int f=1;for(int i=1;i<=len;++i){tem += f*fac[i];f *= 10;} return tem;
}
void dfs(int len, int index)//len是总位数，index是当前构造的是第几位，从数字的高位到低位
{//flag为1，即已经构造了大于n的数了，那么后面再构造也是大于n，不符合条件，直接退出if(flag==1) return;//构造完了最低位，可以进行判断if(index == 0)//判断{int gz = is_int(len);//构造的数字大于n，后面也不用遍历了if(gz > n){flag=1;cout<<ans;return ;}else if(hx[gz]==0)//判断是否之前就已经构造过{hx[gz] = 1;ans++;return ;}return ;}//枚举当前位数的可能值for(int i=1;i<=5;++i){//存值if((index)%2 == 1){fac[index] = ji[i];}else{fac[index] = ou[i];}//递归下一位dfs(len, index-1);}
}
int main()
{cin>>n;//题目的n不超过1e7，最大情况是8位数，所以探讨1-8位数的情况即可for(int i=1;i<=8;i++){if(flag == 1) break;dfs(i,i);}return 0;
}
核心机制
| 机制 | 作用 | 代码体现 |
|---|---|---|
| 动态候选集选择 | 根据位数奇偶自动切换候选数字 | ji[ ],ou[ ]数组 |
| 预判剪枝 | 发现超限立即终止后续构造 | flag标志 |
| 哈希去重 | 避免重复计数 | hx[ ]数字 |
算法性能对比
测试环境：洛谷
| 输入规模 | 暴力法耗时 | 剪枝优化耗时 | 构造法耗时 |
|---|---|---|---|
| 全部测试点 | 284ms | 183ms | 55ms |
- 第一种
- 第二种
- 第三种
思维拓展
进阶优化方向
-
数位DP优化
结合动态规划记录中间状态，将时间复杂度优化至O(logN) -
并行计算
对暴力法进行多线程改造（OpenMP加速）：#pragma omp parallel for reduction(+:ans) for(int i=1;i<=n;i+=2) -
数学公式推导
建立数位长度与可行数的直接关系式，实现O(1)时间复杂度
方法选型指南
| 场景 | 推荐方法 | 理由 |
|---|---|---|
| N≤1e4 | 暴力法 | 实现简单，代码量少 |
| 1e4<N≤1e7 | 剪枝优化 | 平衡实现难度与性能 |
| N>1e7 | 数位构造法 | 时间复杂度最优 |
| 多次查询/预处理 | 构造法+预处理 | 构造结果可缓存复用 |
竞赛技巧：根据数据规模选择策略，1e7是暴力与构造法的性能分水岭（1s限时最多2*1e7）
总结
三种方法体现了算法优化的典型路径：
- 暴力解法：建立问题认知的基础
- 剪枝优化：利用问题特性减少无效计算
- 构造解法：从根本上重构解题思路
通过这组解法，我们不仅解决了具体问题，更展示了算法优化中"观察特性→减少计算→重构思路"的经典方法论。
