第十五届蓝桥杯省赛CB组的第一道填空题叫《好数》。说实话看到题的那一瞬间我有点意外遍历1到2024把每个数字拆开统计每个数字出现次数全是偶数就算好数这不是送分题吗但真正在考场上写下去我才发现这道题藏着至少三个坑偶数次到底怎么判断、数字0在数位DP里怎么处理、以及你算出来的答案到底敢不敢信。这篇文章我把这道题从暴力枚举到位数DP完整拆一遍把我踩过的坑和验算方法一并讲清楚。如果你是准备2026年比赛的选手这篇可以当填空题的复盘模板来读如果你只是好奇这道题怎么解直接看第三部分的手算推导也能秒懂。1. 赛场初见一道看似送分的填空题1.1 题目怎么读才算没读偏题目大意是一个正整数如果它各个数位上的数字出现的次数都是偶数就称为好数。比如11是好数因为数字1出现了2次22也是好数1122还是好数。12不是好数因为数字1和数字2各出现1次1是奇数。现在问1到2024之间一共有多少个这样的数。这里最需要强调的是0次也算偶数。一个自然数11中数字1出现2次数字0、2、3、4一直到9都出现了0次0是偶数所以不影响判定。换句话说判断标准不是“所有数字都必须出现过”而是“所有出现过数字的出现次数都为偶数”。再拿边界值验证一下2024本身是不是好数2出现2次是偶数0出现1次是奇数4出现1次是奇数。所以2024不是好数。这种边界值务必在考场上单独试一遍因为第一题经常有人把边界值想当然。1.2 为什么说这道题考的是“状态意识”很多同学把这道题当成简单的计数题但命题人把它放在B组第一题想让你意识到的其实是一个更核心的东西奇偶状态可以被压缩也可以被翻转。如果把“数字d出现了奇数次还是偶数次”看成一个开关那么每读取一位数字d就相当于拨动一次开关d。最后所有开关都处于“关”的状态这个数就是好数。这个思路就是状态压缩加异或。后面你在做子集枚举、状压DP、甚至线性基的时候会发现大量题目在做同样的事情把一个集合的奇偶性用一个整数表示遇到一个元素就用异或去翻转它。所以这道题在网上热度这么高不只是因为它是蓝桥杯真题更因为它是一个特别好的状态压缩入门题。这也是我愿意单独写一篇博文的原因一道填空题背后的思想比题目本身值钱得多。2. 暴力枚举的写法看清楚每个数字的奇偶次数2.1 check函数的核心逻辑填空题的范围只有2024暴力枚举完全够用。比赛时我建议先写一个绝对不会错的check函数再去想优化。代码非常简单#include bits/stdc.h using namespace std; bool check(int x) { int cnt[10] {0}; while (x 0) { cnt[x % 10]; x / 10; } for (int i 0; i 10; i) { if (cnt[i] 1) return false; } return true; } int main() { int ans 0; for (int i 1; i 2024; i) { if (check(i)) ans; } cout ans \n; return 0; }check函数里cnt[0]到cnt[9]分别记录数字0到9的出现次数。while循环里x % 10取出当前最低位x / 10把最低位移除直到x变成0。最后遍历整个cnt数组只要有一个数字出现了奇数次就返回false全部偶数次才返回true。这个地方有个细节cnt[i] 1和cnt[i] % 2 1完全等价用位运算只是顺手写。如果你觉得不直观用cnt[i] % 2 1也没有任何问题。2.2 手写运行1到2024之间的39个好数这段代码跑完输出结果非常干脆39也就是说1到2024之间一共有39个好数。我当时看到这个数字愣了一下因为直觉上觉得怎么这么少后来分析完才明白三位数一个都没有四位数里又有一堆因为奇数次数被刷掉39是完全合理的。把好数列出来你会发现它们分布得很规律两位数11、22、33、44、55、66、77、88、99共9个四位数1000-1999区间共28个四位数2000-2024区间只有2002和2020共2个。为什么没有一位数和三位数下一节用手算的方式给你讲清楚。2.3 关于答案的两种“手算验证”思路填空题最怕算出一个没把握的答案。我赛后的习惯是暴力代码跑出一个结果再用另一种方法独立验证一次。比如把39个好数全打印出来人工目检这当然可以但效率不高。更聪明的方式是做组合推导把1到2024按位数划成几个区间对每个区间用乘法原理算数量最后加总。只要两个结果一致答案就可以放心填了。下面这一章就是完整的推导过程。3. 拆分区间手算两位数、三位数、四位数的好数分布3.1 一位数到三位数为什么可以直接排除先看一位数。1到9每个数字只出现1次1是奇数所以全部排除一位数没有好数。再看三位数。一个三位数一共有三个数位也就是说所有数字的出现次数加起来等于3。若干个偶数相加是不可能得到3的无论你怎么分都会剩下一个奇数次数。所以三位数一个都没有。两位数稍微特殊一点。两个数字的出现次数加起来等于2只有两种拆法11或者20。11意味着两个不同数字各出现一次两个都是奇数次数不合格20意味着一个数字出现2次另一个数字出现0次也就是aa型的数。a可以从1取到9一共9个11到99。这里顺便验证了“偶数次”和“至少出现一次”的区别。如果错误理解成每个数字都必须出现至少一次两位数就会直接变成0个整道题从头错到尾。3.2 1000-1999区间的组合推演这个区间首位固定是1所以数字1必然出现。为了满足偶数次1的出现次数只能是2次或4次。如果1出现4次那这个数就是1111只有1个。如果1出现2次剩下的两个数位必须由一个相同的数字b填满而且b不能等于1否则1就变成出现4次了。b可以从0、2、3、4、5、6、7、8、9中选一共9种选择。对于每个b另一个1可以放在百位、十位、个位中任意一个位置剩下两个位置填b所以每个b对应3个不同的数。这一段的组合数量是3乘以9等于27个。加上11111000-1999区间一共28个好数。为了让大家方便对照我把每个b对应的三个数列出来b三个数01100、1010、100121122、1212、122131133、1313、133141144、1414、144151155、1515、155161166、1616、166171177、1717、177181188、1818、188191199、1919、1991注意b1的情况没有出现在表里因为它对应的是1111已经单独算过了。3.3 2000-2024区间的两个“幸存者”2000到2024这个区间非常小可以一个一个数但用组合推更快。首位固定是2所以数字2的出现次数必须是偶数也就是2次或4次。2222早就超出2024了排除。所以只能让2出现2次另外两个数位由同一个数字b填满b不能等于2。当b等于0时三种排列是2200、2020、2002。2200已经超过2024舍去2020和2002都在范围内保留。当b等于1时三个数是2112、2121、2211全都大于2024舍去。b大于等于3的时候最小的排列也都超过2024直接舍去。所以2000-2024区间正好2个好数。把前面的结果加起来两位数9个三位数0个1000-1999区间28个2000-2024区间2个总数9加0加28加2等于39。和暴力循环跑出来的结果完全一致。这个手算过程也是填空题的标准验算路径分区间的思路可以推广到任意上界。4. 如果题目改成 n 到 m数位DP求解通用化4.1 状态压缩用10位二进制表示奇偶性如果题目从填空题变成编程题比如问你1到10的9次方之间有多少个好数暴力枚举就扛不住了。这时候需要用数位DP而数位DP的核心就是把“哪些数字出现了奇数次”压缩成一个整数。具体做法是用一个int类型的state它的低10位对应数字0到9。第i位为1表示数字i出现了奇数次第i位为0表示数字i出现了偶数次。初始时什么都没填state等于0。每处理一个数字d就执行state ^ (1 d);因为异或可以把0变1、把1变0正好对应奇偶状态的翻转。最终判断条件就是state等于0表示所有数字都是偶数次。可以想象成一排10个开关每个数字是一根手指来一次就拨动一次对应的开关。只有10个开关全部回到“关”的状态这个数才算通过。4.2 记忆化搜索的C实现数位DP我习惯用记忆化搜索实现比递推写起来更不容易错。下面是完整代码#include bits/stdc.h using namespace std; string s; long long dp[15][1 10][2][2]; long long dfs(int pos, int state, int started, int limit) { if (pos (int)s.size()) { return started state 0; } if (!limit dp[pos][state][started][limit] ! -1) { return dp[pos][state][started][limit]; } long long res 0; int up limit ? s[pos] - 0 : 9; for (int d 0; d up; d) { if (!started d 0) { res dfs(pos 1, state, 0, limit d up); } else { res dfs(pos 1, state ^ (1 d), 1, limit d up); } } if (!limit) { dp[pos][state][started][limit] res; } return res; } long long solve(int n) { s to_string(n); memset(dp, -1, sizeof(dp)); return dfs(0, 0, 0, 1); } int main() { cout solve(2024) \n; return 0; }这里有几个参数需要理解清楚。pos表示当前处理到数字的第几位state表示当前已经填过的数字的奇偶状态started表示是否已经放下了第一个非零数字也就是是否已经“开始”了这个数limit表示当前这一位的取值是否受到上界限制。边界条件是pos等于整个数字串长度时如果started为真并且state为0说明这是一个正整数并且所有数字出现次数都是偶数返回1如果started为假说明整串都是前导零本质上是数字0不能算好数。枚举当前位d的时候如果还没有开始并且d等于0就继续保持started为falsestate不动相当于跳过前导零否则把started置为true并翻转第d位。记忆化只在!limit的情况下进行因为贴合上界时的状态是临时的不能复用不贴合上界时后续所有取值都是0到9自由填结果只和pos、state、started有关可以缓存。solve(2024)跑出来的结果就是39和暴力代码一致。4.3 暴力方案、前缀打表方案、数位DP方案怎么选三种方案的适用场景差别很大我整理了一个表方案适用场景编码量复杂度暴力枚举范围较小一般1e7以下低O(n乘以位数)前缀打表多次查询同一个固定上界中预处理O(n乘以位数)单次查询O(1)数位DP上界可以到1e18中O(位数乘以状态数乘以10)蓝桥杯这道填空题暴力枚举是性价比最高的几毫秒出结果。如果将来看到好数的编程题版本n和m给到10的9次方以上直接用数位DP。如果只是想验证答案写个Python的for循环也行但考场上不允许手算和代码两种能力都得有。我个人后来把这题逻辑扩成了一个区间查询版本用数位DP处理任意区间再配合暴力程序对拍。这种“做一个题就顺手扩展成一个模板”的习惯对备赛很有帮助。5. 现场最容易踩的坑和复盘心得5.1 “偶数次”和“至少两次”的语义陷阱我在考场外听到有同学讨论这道题说“好数就是每个数字至少出现两次”。这个理解在小范围数据里可能碰巧算对但它是错的。举个反例111222这个数1出现3次2出现3次。如果按“至少出现两次”来判定它是好数但按题目要求的“偶数次”它并不是好数。虽然1到2024的范围内碰不到这种数但做题不能依赖“碰巧”换一道范围大的题立刻翻车。正确的检查方式是cnt[i] % 2 0而不是cnt[i] 2。如果你实在不放心也可以写成cnt[i] ! 0 cnt[i] % 2 0不过没有必要因为0次本来就是偶数。5.2 前导零与数字0到底算不算出现暴力枚举不需要考虑这个问题因为整数分解不会保留前导零。但数位DP必须处理否则会出大问题。如果不加started统计到101的时候会把前导的零也算进去觉得0出现了若干次最终把不是好数的101误判成好数答案会比实际偏大。解决方法就是在递归时维护started只有真正开始填非零数字后才把后面的数字计入state。这个细节是很多同学写数位DP时容易漏掉的地方也是填空题和编程题之间的一道分水岭。5.3 一个填空题教会我的三件事第一填空题的暴力不是笨办法而是校验答案的基准线。先写一个逻辑简单的check再跑全范围永远比在脑子里空想要稳。第二状态压缩和异或不是进阶技巧而是竞赛的基本功。这道题里的state ^ (1 d)思维会在后续的状压DP、线性基、异或问题里反复出现建议备赛选手把它吃透。第三比赛比的不是会多少花活而是少犯多少错误。定义题读三遍边界值单独测算完用另一种方法复核这三步做好第一题基本不会失守。最后说一个我自己实践下来的建议拿到这类数位统计题不要只满足于把填空题答案算出来试着把它扩展成“求n到m之间有多少个好数”的通用版本再写个对拍程序验证。整个过程走一遍比盲目刷十道题都管用。