1. 问题引入当“二进制”遇上“蓝桥杯国赛”最近在整理历年蓝桥杯国赛真题时我又重新审视了2021年第十二届国赛的这道“二进制问题”。说实话第一次看到这个标题时我心里咯噔了一下——“二进制问题”这范围也太广了从基础的进制转换到复杂的位运算技巧甚至数位DP都可能被囊括其中。国赛的题目尤其是压轴或准压轴题从来不会只考你“把十进制转成二进制”这么简单。它考的是一种思维一种将数学特性、编程技巧和算法思想融合起来解决具体问题的能力。这道题目的核心我理解下来是围绕一个非常经典的“数位”场景展开的给定一个正整数N我们需要找出在1到N的范围内有多少个数的二进制表示中恰好包含K个1。举个例子如果N5(二进制101)K2那么我们需要统计1(001),2(010),3(011),4(100),5(101) 这些数。其中二进制恰好有2个1的数有3(011) 和5(101)所以答案就是2。你可能会想这还不简单写个循环从1到N每个数转二进制数一下1的个数统计一下不就完了如果N很小比如只有几万、几十万这确实是最直白有效的“暴力枚举”法。但蓝桥杯国赛的题目数据规模往往是用来区分“暴力选手”和“算法选手”的。我敢打赌这道题的N上限绝对会大到让你循环到天荒地老通常是10^18甚至更大。直接枚举时间复杂度是O(N * logN)在N极大时是完全不可行的。这就引出了解决此类问题的核心算法——数位动态规划或者更具体地说是数位DP。数位DP专门用来解决在给定区间[L, R]内满足某种与“数位”相关性质的数的个数问题。这里的“数位”在十进制下就是每一位的数字在二进制下就是每一个比特位是0还是1。它通过“记忆化搜索”的方式避免了逐个数字检查的巨大开销将时间复杂度降低到只与数的位数有关。对于二进制N最大是10^18其二进制位数也不过60位左右因此数位DP可以在极短的时间内解决问题。接下来我将彻底拆解这道题不仅告诉你标准的数位DP解法怎么写还会深入探讨其中的思维细节、容易踩的坑以及如何从“暴力枚举”的思维惯性过渡到“数位统计”的高效思维。我们不止步于AC更要明白为什么这样能AC。2. 从暴力枚举到数位DP的思维跃迁在直接上代码之前我们必须先建立正确的思维模型。理解数位DP关键在于理解它是如何“化整为零”将一个庞大的计数问题分解为对数字每一位的、可控的状态决策问题。2.1 为什么暴力枚举会失效假设题目给定的N最大为10^15。用最朴素的Python代码来暴力求解def count_ones(x): count 0 while x: count x 1 x 1 return count def brute_force(N, K): ans 0 for i in range(1, N 1): if count_ones(i) K: ans 1 return ans我们来粗略估算一下时间。循环10^15次即使每次循环只做极少量的操作比如几十条CPU指令在现代CPU上假设每秒能处理10^9次简单操作也需要10^15 / 10^9 10^6秒这大约是11.5天。这显然超出了任何算法竞赛的时间限制通常是1~2秒。因此暴力法在此路不通。2.2 数位DP的核心思想按位构造与状态记忆数位DP摒弃了“遍历每一个数”的思路转而采用“构造所有满足条件的数”的思路。它把数字看成是一个由数位组成的序列。对于二进制就是一个0/1序列。我们考虑从数字的最高位最左边开始依次向低位确定每一个比特是0还是1。在确定的过程中我们需要记录一些关键的状态以确保最终构造出来的数字不会超过上界N并且满足“恰好有K个1”的条件。这里引入数位DP中最重要的两个概念数位位置pos当前正在处理的是从高到低的第几位通常从最高位开始pos递减。状态state到当前位置为止我们已经使用了多少个1。这是为了最终检查是否恰好用了K个。限制标志limit这是一个非常关键的状态。它表示当前位在选择数字时是否受到上界N对应位的限制。如果limitTrue意味着之前所有高位构造的数字都和N的对应位完全相等。那么当前位能选择的最大值不能超过N在当前位的值0或1。如果limitFalse意味着之前的高位已经有至少一位比N的对应位小了。那么当前位可以自由选择0或1因为无论怎么选最终构造的数都肯定小于N。举个例子假设N 5二进制为101。我们从最高位第2位值为1开始此时limitTrue当前位只能选0或1。如果我们选0那么由于0 1从此以后后面的所有位都不再受N的限制limit变为False可以自由选择0或1。如果我们选1那么当前位和N的这一位相等limit仍然为True继续传递给下一位。接下来处理第二位值为0如果此时limitTrue那么当前位最大只能选0因为N的这一位是0。如果我们选了0limit保持True如果我们选了1那构造的数就大于N了这是不允许的。如果此时limitFalse那么我们可以自由选0或1。通过limit这个状态我们巧妙地控制了构造过程使其能覆盖所有[0, N]之间的数且不重不漏。2.3 记忆化搜索避免重复计算的利器在递归构造的过程中我们会遇到大量相同的子问题。例如当pos3处理第3低位state1已经用了1个1且limitFalse无限制时无论之前的高位具体是什么从这个状态往后继续构造所能得到的符合条件的数字个数是完全相同的。如果我们不记录这个结果就会在递归树的不同分支中重复计算完全相同的子问题造成指数级的时间浪费。记忆化搜索Memoization就是用来解决这个问题的。我们用一个数组dp[pos][state]来记录在特定pos和state下当limitFalse时的计算结果。注意limitTrue的状态不能记忆化因为limitTrue意味着紧贴上限N这种情况是唯一的依赖于N的具体值不同分支不共享。有了记忆化每个(pos, state, limit)的组合最多只被计算一次。由于pos最多60位state最多60个1所以总状态数大约在60 * 60 3600这个量级计算量变得微不足道。这就是数位DP能将指数复杂度降为多项式复杂度的魔法所在。3. 解题框架搭建与关键代码实现理解了思想我们来看具体的代码实现。我会用Python来演示因为其清晰的语法更适合表达算法逻辑。整个解法的核心是一个深度优先搜索DFS函数。3.1 数据结构与函数定义首先我们需要将上界N转换为二进制位数组bits并确定其长度m。def solve(N, K): # 将N转换为二进制列表高位在前。例如 N5 - [1, 0, 1] bits [] temp N while temp: bits.append(temp 1) temp 1 bits.reverse() # 反转后得到从高位到低位的列表 if not bits: # 处理N0的情况但题目通常从1开始这里为了完整性 bits [0] m len(bits) # 记忆化数组 dp[pos][cnt] # 初始化为-1表示未计算。pos范围[0, m], cnt范围[0, K] dp [[-1] * (K 1) for _ in range(m)]接下来是核心的DFS函数def dfs(pos, cnt, limit): 递归搜索函数。 :param pos: 当前处理到的二进制位索引从最高位0开始 :param cnt: 到当前位为止已经使用的1的个数 :param limit: 当前位是否受到上界N的限制 :return: 从当前状态开始能构造出的满足条件的数字个数 # 递归边界如果已经处理完所有位 if pos m: # 当所有位都处理完检查使用的1的个数是否恰好为K return 1 if cnt K else 0 # 记忆化只有在无限制(limitFalse)时结果才是可以复用的 if not limit and dp[pos][cnt] ! -1: return dp[pos][cnt] # 确定当前位可以选择的上限 up bits[pos] if limit else 1 res 0 # 遍历当前位所有可能的选择 (0 或 1但不能超过up) for digit in range(up 1): next_cnt cnt if digit 1: next_cnt cnt 1 # 如果当前选择的1的个数已经超过K后续无论如何都不可能满足条件剪枝 if next_cnt K: continue # 决定下一位的limit状态 # 当前位受到限制(limitTrue) 且 当前位选择了上限值(digit up)则下一位继续受限 # 否则下一位不再受限 next_limit limit and (digit up) res dfs(pos 1, next_cnt, next_limit) # 记录记忆化结果仅当无限制时 if not limit: dp[pos][cnt] res return res3.2 主逻辑与初始化调用DFS函数定义好后主逻辑就非常清晰了。我们从最高位pos0开始初始已使用1的个数cnt0并且初始状态是受到限制的limitTrue因为我们构造的数不能超过N。# 从最高位开始搜索初始状态已放置0个1且受到上限限制 ans dfs(0, 0, True) return ans一个至关重要的细节我们的DFS函数计算的是区间[0, N]内满足条件的数的个数。而题目要求通常是[1, N]。因此如果K 0我们需要减去数字0的贡献因为0的二进制表示中1的个数为0。但在这道题中K通常大于0且N大于0所以数字0本身就不会被计入cntK0在posm时才成立但我们的cnt初始为0且K0所以不会统计0。为了代码的通用性我们可以这样处理ans dfs(0, 0, True) # 如果K为0需要减去数字0如果题目范围是[1,N] if K 0: ans - 1 return ans将以上所有部分组合起来就得到了完整的解题代码。这个模板是解决“二进制中1的个数”类数位DP问题的通用框架稍加修改就能应对很多变种题目。4. 深度剖析状态设计与剪枝优化虽然上面的代码已经可以高效解决问题但我们可以更深入地思考其中的设计选择和优化空间。4.1 状态定义的多样性在上面的解法中我们的状态是(pos, cnt, limit)并用dp[pos][cnt]来记忆化limitFalse的情况。这是最直观的一种设计。另一种常见的设计是将limit也作为记忆化数组的一个维度即dp[pos][cnt][limit]。这样逻辑上更统一代码可能更简洁但空间开销会翻倍因为limit有2种状态。在本题中cnt最大为60pos最大为60所以dp[61][61][2]的空间完全可以接受不到10KB。这种写法可以避免在记忆化时判断limit的条件对初学者来说可能更不容易出错。# 另一种状态设计示例 dp [[[-1] * 2 for _ in range(K1)] for _ in range(m)] def dfs(pos, cnt, limit): if pos m: return 1 if cnt K else 0 if dp[pos][cnt][limit] ! -1: return dp[pos][cnt][limit] ... dp[pos][cnt][limit] res return res两种方式都是正确的选择哪一种取决于个人习惯和对效率的极致追求第一种节省一半空间。4.2 重要的剪枝策略在DFS函数中我们有一处显式的剪枝if next_cnt K: continue这处剪枝至关重要。它意味着如果在构造过程中已经使用的1的个数超过了目标K那么无论后面位怎么选即使全选0最终这个数的1的个数也必然大于K不可能满足条件。因此这个分支可以直接放弃不再继续递归。这个剪枝能显著减少不必要的搜索路径提升效率。4.3 处理前导零的思考在十进制数位DP中“前导零”常常是一个需要特别处理的问题因为它会影响数字的位数比如“0123”和“123”是不同的表示但数值相同。在二进制中前导零通常不是问题。因为二进制表示本身就不包含前导零除了数字0本身。在我们的构造过程中我们从最高非零位开始构造自然就没有前导零的困扰。这也是二进制数位DP往往比十进制更简单一点的原因。但是有一种情况需要小心如果题目问的是“二进制形式下”有时会包括前导零以达到某个固定长度。这时就需要在状态中增加一个is_start标志表示是否已经开始构造非零位即是否跳过了前导零。本题显然不需要。5. 测试、调试与常见“坑点”理论正确不代表代码一次就能AC。在实际编写和调试数位DP时有几个地方特别容易出错。5.1 边界条件测试一定要用多种边界数据测试你的程序极小值N1, K0;N1, K1。检查对于最小输入程序是否正常运行并返回正确结果注意题目范围是否包含0。相等情况N本身恰好满足条件时。例如N7(二进制111)K3答案应该包含N本身。K值过大K大于N的二进制位数时答案显然应该是0。例如N8(二进制1000共4位)K5。你的程序应该能快速返回0而不是进入深层递归或出错。我们的剪枝if next_cnt K: continue能很好地处理这种情况。大数测试用N10^15量级K取中间值比如30进行测试。可以先用暴力算法在小范围如N1000内验证数位DP结果的正确性确保逻辑无误后再测试大数。5.2 记忆化数组的初始化与下标初始化值记忆化数组必须初始化为一个不可能被正常计算得到的值比如-1。不能初始化为0因为0可能是一个有效的计算结果表示该状态无法构造出任何符合条件的数。数组大小dp数组的第一维大小是m二进制位数第二维大小是K1因为cnt的范围是[0, K]。务必确保K的最大值在合理范围内如果题目给出的K可能很大比如接近60数组大小就是61*61没问题。但如果K可能大于位数我们可以进行优化第二维大小取min(K, m)1即可因为cnt不可能超过总位数m。下标访问在递归中当cnt K时next_cnt cnt 1就会等于K1。在访问dp[pos][next_cnt]之前必须确保next_cnt K否则会导致数组越界。我们的剪枝if next_cnt K: continue正好防止了这种情况。5.3 递归深度与性能Python的默认递归深度限制大约是1000层。对于位数最多60的二进制问题递归深度最多61层远远低于限制所以不用担心栈溢出。但在某些复杂的十进制数位DP中位数可能达到20递归深度也是安全的。性能方面每个状态最多计算一次计算量是O(m * K)对于m60, K60的情况计算次数在万次以下运行时间远小于1秒完全满足竞赛要求。6. 举一反三数位DP的变体与应用掌握了这道“二进制问题”的解法你就掌握了数位DP最核心的模板。这个模板可以解决一大类问题。我们来看看几个变体思考如何修改我们的代码变体1十进制下统计 [L, R] 内数位之和为 S 的数字个数。改动将二进制位数组bits改为十进制位数组。up的计算改为up bits[pos] if limit else 9。状态cnt的含义变为“当前数位之和”。注意十进制需要考虑前导零吗对于数位和前导零不影响结果000所以通常不需要特殊处理。变体2统计 [1, N] 内二进制表示中“1的个数”是“0的个数”的整数倍的数的个数。改动状态需要记录两个信息当前1的个数cnt1和当前0的个数cnt0或者总位数pos和cnt1因为cnt0 pos - cnt1。递归边界时判断cnt1 0 and cnt1 % (pos - cnt1) 0。状态维度增加记忆化数组变为dp[pos][cnt1]假设limitFalse。变体3求 [L, R] 内满足某种条件的所有数字的“和”而不仅仅是“个数”。改动这是数位DP的进阶问题。我们的DFS函数不能只返回个数还需要返回一个“状态结构体”里面包含(count, sum)两个信息。在递归合并结果时需要计算新的和 左子树的和 右子树的和 (当前位数字 * 10^{当前位权重} * 子树的个数)。这需要更精细的状态设计和结果合并。通过这道蓝桥杯国赛真题我们深入剖析了数位DP这一利器。它看似复杂但核心思想就是按位决策、状态记忆、限制传递。遇到此类问题时先冷静分析“数位”和“限制条件”设计出合适的状态然后套用DFS记忆化的框架问题往往就能迎刃而解。多练习几道不同变体的题目你就能真正掌握这种将大问题分解为小状态的艺术。