拓冰网站定制 
1. 项目概述一道经典的国赛题“凑平方数”是2016年第七届蓝桥杯国赛C B组的一道编程题。这道题之所以在众多竞赛题目中脱颖而出被许多选手和教练反复提及甚至成为讲解“位运算”灵活运用的经典案例是因为它完美地将一个看似复杂的组合数学问题转化为了一个可以用高效状态压缩技巧解决的搜索问题。题目本身并不要求你掌握多么高深的数学定理而是考验你能否跳出常规的循环与递归思维利用计算机底层的数据表示方式——二进制位来优雅地表示和操作“状态”。简单来说题目给出了0-9这十个数字每个数字恰好使用一次。你需要将它们排列组合分割成若干个数字不允许有前导零使得每个数字本身都是一个完全平方数。你的任务是计算所有可能的分割方案总数。例如数字序列“0 1 4 9 25 36 784”就是一种合法的分割对应平方数0 1 4 9 25 36 784。初看此题很多人的第一反应是深度优先搜索DFS去尝试所有分割点然后判断每个分割出来的数字是否为平方数。这个思路本身没有错但实现起来尤其是在处理数字重复使用判断和状态记录上会显得非常笨拙且容易超时。这时“位运算”就闪亮登场了。这道题的核心价值在于它教会我们如何用一个整数的二进制位来表征一个集合。0-9这十个数字我们可以用10个二进制位来表示它们的使用情况第i位为1表示数字i已经被使用了。这样一来检查数字是否重复、记录当前使用了哪些数字都可以通过位运算在常数时间内完成。这种技巧将问题的维度从具体的数字序列提升到了抽象的“状态”层面使得搜索过程可以基于“状态”进行记忆化极大地提升了效率。接下来我们就深入拆解这道题看看如何将位运算的威力发挥到极致。2. 核心思路与位运算设计面对“凑平方数”这道题我们首先要摒弃“操作字符串”或“操作整数数组”的惯性思维。题目本质是从数字集合{012... 9}中选取若干个不相交的子集每个子集构成的数字按一定顺序排列是一个完全平方数并且所有子集的并集恰好是全集。这里的“顺序”很重要因为数字排列不同构成的整数就不同。但我们可以换个角度先不考虑全集的划分而是考虑我们能否逐步“构造”出一些平方数并且它们使用的数字不冲突。2.1 状态压缩用整数表示集合这是整个解法最精妙的一步。我们用一个10位的二进制整数state来表示0-9这十个数字的使用情况。约定二进制的最低位第0位代表数字0的使用情况。第1位代表数字1以此类推第9位代表数字9。如果某一位是1表示对应的数字已经被使用过了如果是0则表示尚未使用。例如state 0(二进制0000000000) 表示所有数字都未使用。state 3(二进制0000000011) 表示数字0和数字1已被使用。state 1023(二进制1111111111) 表示所有数字0-9都已被使用。有了这个表示法我们可以用位运算高效地实现集合操作检查数字d是否已被使用(state d) 1。将state右移d位再与1进行按位与结果为1则表示已使用。标记数字d为已使用state | (1 d)。生成一个只有第d位为1的数然后与state进行按位或。判断状态b是否是状态a的子集(a b) b。如果b的所有1位在a中也是1则b是a的子集。2.2 算法框架基于状态的深度优先搜索DFS我们的目标是找到所有能将state从0全空变成1023全满的方案并且每次变化都是“添加”一个合法的平方数这个平方数所使用的数字集合是当前未使用数字集合的一个子集。因此算法可以设计为预处理生成所有由0-9中若干数字构成、且本身是完全平方数的“候选平方数”。同时记录每个候选平方数所使用的数字集合用位掩码表示。深度优先搜索DFS从初始状态state 0开始搜索。当前状态为cur_state。遍历所有候选平方数对于某个候选平方数square其数字集合掩码为mask。如果mask是cur_state的补集的子集即mask中的数字在cur_state中都未被使用那么可以选择这个平方数。将状态更新为cur_state | mask然后进行下一层递归。如果更新后的状态等于1023则找到一种合法方案方案数加1。去重与剪枝由于平方数选择的顺序不同可能被视为同一种划分方案例如先选1再选4和先选4再选1最终划分结果都是{1 4}我们需要去重。一个有效的方法是在DFS时规定一个“顺序”例如要求每次选择的平方数对应的数值是非递减的。这样可以避免因顺序不同导致的重复计数。2.3 为什么是DFS而不是动态规划这是一个很好的思考点。理论上这个问题具有“最优子结构”最终状态由子状态组合而成和“无后效性”当前状态只取决于使用了哪些数字而不取决于这些数字是以何种顺序、被哪些平方数使用的可以用动态规划DP解决。我们可以定义dp[state]为达到状态state的方案数。状态转移方程为dp[state] dp[state ^ mask]其中mask是某个候选平方数的掩码并且mask是state的子集。最后dp[1023]就是答案。那么为什么很多题解采用DFS呢主要有两个原因直观性对于搜索类题目DFS的框架更容易理解和实现尤其是结合递归和回溯逻辑清晰。去重处理的便利性在DFS中通过强制规定选择平方数的顺序如非递减可以非常自然地在递归过程中避免重复枚举同一组合。而在DP中如果直接使用上述转移方程会把{1 4}和{4 1}算作两种不同的方案需要更复杂的去重手段例如对平方数排序后在转移时增加“最后一个选择的平方数”这一维度增加了状态复杂度。因此DFS剪枝顺序性剪枝在这个问题上是更简洁、更常用的解法。当然使用DP也是完全可行的并且是更通用的解法尤其当数字范围更大时可能体现出优势。3. 关键实现细节与代码剖析理解了核心思路后我们来看具体的实现。我将以C为例一步步拆解代码并解释每个关键步骤背后的意图。3.1 预处理生成候选平方数我们需要的候选平方数其每一位数字必须在0-9之间且不能有重复数字因为题目要求0-9各用一次一个平方数内部自然也不能重复。同时它本身必须是完全平方数。#include iostream #include vector #include cmath #include algorithm using namespace std; vectorpairlong long int squares; // 存储平方数值 对应的数字集合掩码 // 检查数字num是否由不重复的0-9数字构成并返回其位掩码 int getMask(long long num) { if (num 0) return 1 0; // 数字0单独处理 int mask 0; while (num 0) { int digit num % 10; if ((mask digit) 1) { // 如果数字重复出现 return -1; // 返回-1表示无效 } mask | (1 digit); num / 10; } return mask; } void preprocess() { // 估算平方数的上限最大的10位不重复数字是9876543210但其平方根远小于这个数。 // 实际上由0-9中部分数字构成的最大平方数不会超过10^10级别。 // 我们可以遍历平方根。sqrt(9876543210) ≈ 99380我们取一个稍大的范围。 for (long long i 0; i 100000; i) { long long sq i * i; int mask getMask(sq); if (mask ! -1) { // 如果平方数由不重复数字构成 squares.push_back({sq mask}); } } // 排序便于DFS时进行顺序性剪枝 sort(squares.begin() squares.end()); }注意getMask函数中对num0的特殊处理至关重要。因为while(num0)的循环无法处理num0的情况而0本身是一个合法的平方数0*00其掩码就是10。3.2 DFS搜索实现DFS函数需要记录当前已使用的数字状态curState以及上一次选择的平方数在数组中的索引lastIdx用于顺序性剪枝。long long ans 0; // 最终方案数可能很大用long long const int FULL_STATE (1 10) - 1; // 1023 表示所有数字都用完了 void dfs(int curState int lastIdx) { if (curState FULL_STATE) { ans; return; } // 从lastIdx之后开始遍历保证选择的平方数数值非递减 for (int i lastIdx; i squares.size(); i) { long long sqVal squares[i].first; int mask squares[i].second; // 剪枝1如果当前平方数所需的数字与已用数字有重叠则跳过 if (curState mask) continue; // 剪枝2可选如果剩余未用的数字个数小于当前平方数的位数理论上可以跳过但这里不是主要瓶颈。 // 选择当前平方数进入下一层递归 dfs(curState | mask i); // 注意这里传入的lastIdx是i保证了下一层只能选i及之后的平方数 } }关键点解析参数lastIdx这是实现顺序性剪枝的核心。dfs(curState | mask i)中的i确保了下一层递归只能选择索引大于等于i的平方数。因为数组squares已经按平方数值从小到大排序这就等价于要求每次新加入的平方数不小于上一次加入的平方数。这完美地避免了因顺序不同导致的重复计数。递归终止条件curState FULL_STATE。当所有数字都被使用时找到一种合法划分方案。剪枝操作if (curState mask) continue;这是位运算的典型应用。按位与的结果不为0说明mask表示的集合与当前已用集合curState有交集即数字冲突不能选择。3.3 主函数与初始化int main() { preprocess(); // 预处理所有候选平方数 cout Total candidate squares: squares.size() endl; dfs(0 0); // 从状态0开始搜索并且可以从第一个平方数开始选 cout The answer is: ans endl; return 0; }运行这段代码你就可以得到“凑平方数”这道题的最终答案。在我的机器上运行预处理生成了大约几百个候选平方数DFS搜索过程瞬间完成。4. 位运算技巧的深度扩展通过“凑平方数”这道题我们领略了位运算在状态压缩中的强大威力。但这仅仅是开始。位运算的技巧博大精深在算法竞赛和底层开发中应用极广。我们来延伸一下看看还有哪些常见的位运算“骚操作”。4.1 枚举子集这是状态压缩DP中的核心操作。给定一个集合掩码state如何高效地枚举它的所有子集int sub state; do { // 对子集sub进行处理 // ... sub (sub - 1) state; // 关键获取下一个子集 } while (sub ! state); // 当sub减到0再与state运算后会变成state循环结束这个循环会枚举state的所有子集包括空集和自身。例如state 5 (101b)枚举顺序是5(101)4(100)1(001)0(000)。这个技巧在“凑平方数”的DP解法中会用到。4.2 最低位1Lowbit与统计1的个数Lowbitx -x。这个操作可以取出一个整数二进制表示中最低位的1及其后面的0。例如x12(1100b)lowbit 4(100b)。这在树状数组Fenwick Tree中是基础操作。统计1的个数Popcount内置函数__builtin_popcount(state)GCC/Clang。手动计算int countBits(int n) { int count 0; while (n) { n (n - 1); // 每次操作消去最低位的1 count; } return count; }4.3 状态压缩动态规划DP解法作为对DFS解法的补充我们来看一下DP解法。这能帮助我们更好地理解状态之间的转移关系。long long dp[1 10] {0}; // dp[state] 表示达到状态state的方案数 dp[0] 1; // 初始状态一个数都不选视为1种方案 // 对每个候选平方数已经过排序和去重 for (auto [sqVal mask] : squares) { // 倒序遍历所有状态这是01背包“每种物品只有一个”的思想 // 正序遍历会导致一个平方数被重复使用多次 for (int state FULL_STATE; state 0; --state) { // 如果当前状态state包含mask这个子集并且state-mask这个状态是可达的 if ((state mask) mask) { // 等价于 mask 是 state 的子集 dp[state] dp[state ^ mask]; // state ^ mask 就是从state中移除mask集合 } } } cout DP Answer: dp[FULL_STATE] endl;重要提示上面的DP代码存在重复计数问题因为它把{1 4}和{4 1}当成了两种方案。为了解决这个问题我们需要引入“顺序”的概念。一个经典的方法是使用“枚举子集”的技巧并配合平方数排序但实现起来比DFS复杂。这也是为什么DFS顺序剪枝在该问题上更受欢迎的原因。DP解法更通用的形式是“状态压缩DP枚举子集”其正确实现需要保证划分的无序性通常需要对平方数进行排序并在转移时增加限制或者使用另一种状态定义方式。5. 调试技巧与常见问题即便思路清晰在实现过程中也可能遇到各种“坑”。下面分享一些我在实现和调试这道题时总结的经验。5.1 问题一答案总是偏大这是最常见的问题几乎百分之百是因为方案去重没做好。症状运行程序得出的答案比标准答案大很多。诊断你的程序很可能把同一种数字划分方案因平方数加入顺序不同而重复计算了多次。例如全集{0123456789}被划分为{1 4} {9} {25} {36} {0} {784}。如果你的DFS允许先选9再选1或者先选1再选9最终都被计入那么方案数就会翻倍。解决确保在DFS中加入了顺序性剪枝即参数lastIdx。仔细检查递归调用dfs(nextState i)而不是dfs(nextState 0)或dfs(nextState lastIdx1)。i保证了后续选择的平方数索引不小于当前结合预处理排序就保证了数值非递减。5.2 问题二预处理时漏掉了平方数0症状答案比标准答案略小。诊断在getMask函数中while(num0)循环会直接跳过num0的情况导致平方数0没有被加入候选列表。而0是一个合法的平方数00*0并且它只使用数字0是许多有效方案的一部分。解决在getMask函数开头增加对num0的特殊判断直接返回1 0。5.3 问题三递归深度过深或运行超时症状程序运行缓慢甚至栈溢出。诊断虽然状态只有1024种但DFS的递归分支可能很多。如果预处理生成的候选平方数过多比如没有检查数字重复把121这样有重复数字的平方数也加进去了或者剪枝不够有效会导致递归树非常庞大。解决加强预处理过滤确保getMask函数正确过滤掉包含重复数字的平方数。验证剪枝确保if (curState mask) continue;这一行代码正确无误。使用迭代加深或DP如果递归确实太深可以考虑用栈模拟递归或者直接使用状态压缩DP的迭代写法。对于本题正确的DFS效率是极高的超时通常意味着代码有逻辑错误。5.4 一个实用的调试方法打印关键路径当答案不对时可以修改DFS函数让它打印出找到的合法方案这样能直观地看到重复或遗漏。vectorlong long path; // 记录当前路径上的平方数 void dfs_debug(int curState int lastIdx) { if (curState FULL_STATE) { for (auto val : path) cout val ; cout endl; ans; return; } for (int i lastIdx; i squares.size(); i) { // ... 判断条件 ... path.push_back(squares[i].first); dfs_debug(curState | squares[i].second i); path.pop_back(); // 回溯 } }通过观察打印出的方案序列你可以快速判断去重逻辑是否生效序列应该是非递减的以及是否包含了所有可能的平方数。6. 从这道题到更广阔的的应用“凑平方数”虽然是一道竞赛题但其蕴含的“状态压缩”思想具有极高的实用价值。它本质上解决了一类“集合划分”或“集合覆盖”问题这类问题在资源分配、任务调度、电路设计等领域都有出现。核心思想迁移当你遇到一个问题其状态可以用一个规模不大的集合通常元素数20因为2^20约等于100万是计算机可处理的范围来表示并且状态转移涉及集合的并、交、补运算时就应该立即想到状态压缩和位运算。举例旅行商问题TSP的经典DP解法用dp[mask][i]表示访问过城市集合mask最后停留在城市i的最短路径。mask就是一个状态压缩的整数。棋盘覆盖问题用二进制表示一行的格子状态如1表示已覆盖0表示未覆盖通过位运算判断上下行状态的兼容性。权限管理系统用不同的二进制位表示不同的操作权限如读、写、执行、删除。一个用户的权限集就是一个整数检查权限就是位与操作。掌握位运算不仅仅是学会了几种操作符更是掌握了一种高效建模复杂状态的思维方式。它让我们的程序能从繁琐的数组操作中解放出来直接操作“状态”这个整体既提升了效率也简化了逻辑。下次当你再遇到看似复杂的组合问题时不妨先想一想“我能不能用一个整数的二进制位来表示它”这或许就是打开高效解法之门的钥匙。 蓝桥杯国赛题解：巧用位运算状态压缩解决“凑平方数”问题
1. 项目概述一道经典的国赛题“凑平方数”是2016年第七届蓝桥杯国赛C B组的一道编程题。这道题之所以在众多竞赛题目中脱颖而出被许多选手和教练反复提及甚至成为讲解“位运算”灵活运用的经典案例是因为它完美地将一个看似复杂的组合数学问题转化为了一个可以用高效状态压缩技巧解决的搜索问题。题目本身并不要求你掌握多么高深的数学定理而是考验你能否跳出常规的循环与递归思维利用计算机底层的数据表示方式——二进制位来优雅地表示和操作“状态”。简单来说题目给出了0-9这十个数字每个数字恰好使用一次。你需要将它们排列组合分割成若干个数字不允许有前导零使得每个数字本身都是一个完全平方数。你的任务是计算所有可能的分割方案总数。例如数字序列“0 1 4 9 25 36 784”就是一种合法的分割对应平方数0 1 4 9 25 36 784。初看此题很多人的第一反应是深度优先搜索DFS去尝试所有分割点然后判断每个分割出来的数字是否为平方数。这个思路本身没有错但实现起来尤其是在处理数字重复使用判断和状态记录上会显得非常笨拙且容易超时。这时“位运算”就闪亮登场了。这道题的核心价值在于它教会我们如何用一个整数的二进制位来表征一个集合。0-9这十个数字我们可以用10个二进制位来表示它们的使用情况第i位为1表示数字i已经被使用了。这样一来检查数字是否重复、记录当前使用了哪些数字都可以通过位运算在常数时间内完成。这种技巧将问题的维度从具体的数字序列提升到了抽象的“状态”层面使得搜索过程可以基于“状态”进行记忆化极大地提升了效率。接下来我们就深入拆解这道题看看如何将位运算的威力发挥到极致。2. 核心思路与位运算设计面对“凑平方数”这道题我们首先要摒弃“操作字符串”或“操作整数数组”的惯性思维。题目本质是从数字集合{012... 9}中选取若干个不相交的子集每个子集构成的数字按一定顺序排列是一个完全平方数并且所有子集的并集恰好是全集。这里的“顺序”很重要因为数字排列不同构成的整数就不同。但我们可以换个角度先不考虑全集的划分而是考虑我们能否逐步“构造”出一些平方数并且它们使用的数字不冲突。2.1 状态压缩用整数表示集合这是整个解法最精妙的一步。我们用一个10位的二进制整数state来表示0-9这十个数字的使用情况。约定二进制的最低位第0位代表数字0的使用情况。第1位代表数字1以此类推第9位代表数字9。如果某一位是1表示对应的数字已经被使用过了如果是0则表示尚未使用。例如state 0(二进制0000000000) 表示所有数字都未使用。state 3(二进制0000000011) 表示数字0和数字1已被使用。state 1023(二进制1111111111) 表示所有数字0-9都已被使用。有了这个表示法我们可以用位运算高效地实现集合操作检查数字d是否已被使用(state d) 1。将state右移d位再与1进行按位与结果为1则表示已使用。标记数字d为已使用state | (1 d)。生成一个只有第d位为1的数然后与state进行按位或。判断状态b是否是状态a的子集(a b) b。如果b的所有1位在a中也是1则b是a的子集。2.2 算法框架基于状态的深度优先搜索DFS我们的目标是找到所有能将state从0全空变成1023全满的方案并且每次变化都是“添加”一个合法的平方数这个平方数所使用的数字集合是当前未使用数字集合的一个子集。因此算法可以设计为预处理生成所有由0-9中若干数字构成、且本身是完全平方数的“候选平方数”。同时记录每个候选平方数所使用的数字集合用位掩码表示。深度优先搜索DFS从初始状态state 0开始搜索。当前状态为cur_state。遍历所有候选平方数对于某个候选平方数square其数字集合掩码为mask。如果mask是cur_state的补集的子集即mask中的数字在cur_state中都未被使用那么可以选择这个平方数。将状态更新为cur_state | mask然后进行下一层递归。如果更新后的状态等于1023则找到一种合法方案方案数加1。去重与剪枝由于平方数选择的顺序不同可能被视为同一种划分方案例如先选1再选4和先选4再选1最终划分结果都是{1 4}我们需要去重。一个有效的方法是在DFS时规定一个“顺序”例如要求每次选择的平方数对应的数值是非递减的。这样可以避免因顺序不同导致的重复计数。2.3 为什么是DFS而不是动态规划这是一个很好的思考点。理论上这个问题具有“最优子结构”最终状态由子状态组合而成和“无后效性”当前状态只取决于使用了哪些数字而不取决于这些数字是以何种顺序、被哪些平方数使用的可以用动态规划DP解决。我们可以定义dp[state]为达到状态state的方案数。状态转移方程为dp[state] dp[state ^ mask]其中mask是某个候选平方数的掩码并且mask是state的子集。最后dp[1023]就是答案。那么为什么很多题解采用DFS呢主要有两个原因直观性对于搜索类题目DFS的框架更容易理解和实现尤其是结合递归和回溯逻辑清晰。去重处理的便利性在DFS中通过强制规定选择平方数的顺序如非递减可以非常自然地在递归过程中避免重复枚举同一组合。而在DP中如果直接使用上述转移方程会把{1 4}和{4 1}算作两种不同的方案需要更复杂的去重手段例如对平方数排序后在转移时增加“最后一个选择的平方数”这一维度增加了状态复杂度。因此DFS剪枝顺序性剪枝在这个问题上是更简洁、更常用的解法。当然使用DP也是完全可行的并且是更通用的解法尤其当数字范围更大时可能体现出优势。3. 关键实现细节与代码剖析理解了核心思路后我们来看具体的实现。我将以C为例一步步拆解代码并解释每个关键步骤背后的意图。3.1 预处理生成候选平方数我们需要的候选平方数其每一位数字必须在0-9之间且不能有重复数字因为题目要求0-9各用一次一个平方数内部自然也不能重复。同时它本身必须是完全平方数。#include iostream #include vector #include cmath #include algorithm using namespace std; vectorpairlong long int squares; // 存储平方数值 对应的数字集合掩码 // 检查数字num是否由不重复的0-9数字构成并返回其位掩码 int getMask(long long num) { if (num 0) return 1 0; // 数字0单独处理 int mask 0; while (num 0) { int digit num % 10; if ((mask digit) 1) { // 如果数字重复出现 return -1; // 返回-1表示无效 } mask | (1 digit); num / 10; } return mask; } void preprocess() { // 估算平方数的上限最大的10位不重复数字是9876543210但其平方根远小于这个数。 // 实际上由0-9中部分数字构成的最大平方数不会超过10^10级别。 // 我们可以遍历平方根。sqrt(9876543210) ≈ 99380我们取一个稍大的范围。 for (long long i 0; i 100000; i) { long long sq i * i; int mask getMask(sq); if (mask ! -1) { // 如果平方数由不重复数字构成 squares.push_back({sq mask}); } } // 排序便于DFS时进行顺序性剪枝 sort(squares.begin() squares.end()); }注意getMask函数中对num0的特殊处理至关重要。因为while(num0)的循环无法处理num0的情况而0本身是一个合法的平方数0*00其掩码就是10。3.2 DFS搜索实现DFS函数需要记录当前已使用的数字状态curState以及上一次选择的平方数在数组中的索引lastIdx用于顺序性剪枝。long long ans 0; // 最终方案数可能很大用long long const int FULL_STATE (1 10) - 1; // 1023 表示所有数字都用完了 void dfs(int curState int lastIdx) { if (curState FULL_STATE) { ans; return; } // 从lastIdx之后开始遍历保证选择的平方数数值非递减 for (int i lastIdx; i squares.size(); i) { long long sqVal squares[i].first; int mask squares[i].second; // 剪枝1如果当前平方数所需的数字与已用数字有重叠则跳过 if (curState mask) continue; // 剪枝2可选如果剩余未用的数字个数小于当前平方数的位数理论上可以跳过但这里不是主要瓶颈。 // 选择当前平方数进入下一层递归 dfs(curState | mask i); // 注意这里传入的lastIdx是i保证了下一层只能选i及之后的平方数 } }关键点解析参数lastIdx这是实现顺序性剪枝的核心。dfs(curState | mask i)中的i确保了下一层递归只能选择索引大于等于i的平方数。因为数组squares已经按平方数值从小到大排序这就等价于要求每次新加入的平方数不小于上一次加入的平方数。这完美地避免了因顺序不同导致的重复计数。递归终止条件curState FULL_STATE。当所有数字都被使用时找到一种合法划分方案。剪枝操作if (curState mask) continue;这是位运算的典型应用。按位与的结果不为0说明mask表示的集合与当前已用集合curState有交集即数字冲突不能选择。3.3 主函数与初始化int main() { preprocess(); // 预处理所有候选平方数 cout Total candidate squares: squares.size() endl; dfs(0 0); // 从状态0开始搜索并且可以从第一个平方数开始选 cout The answer is: ans endl; return 0; }运行这段代码你就可以得到“凑平方数”这道题的最终答案。在我的机器上运行预处理生成了大约几百个候选平方数DFS搜索过程瞬间完成。4. 位运算技巧的深度扩展通过“凑平方数”这道题我们领略了位运算在状态压缩中的强大威力。但这仅仅是开始。位运算的技巧博大精深在算法竞赛和底层开发中应用极广。我们来延伸一下看看还有哪些常见的位运算“骚操作”。4.1 枚举子集这是状态压缩DP中的核心操作。给定一个集合掩码state如何高效地枚举它的所有子集int sub state; do { // 对子集sub进行处理 // ... sub (sub - 1) state; // 关键获取下一个子集 } while (sub ! state); // 当sub减到0再与state运算后会变成state循环结束这个循环会枚举state的所有子集包括空集和自身。例如state 5 (101b)枚举顺序是5(101)4(100)1(001)0(000)。这个技巧在“凑平方数”的DP解法中会用到。4.2 最低位1Lowbit与统计1的个数Lowbitx -x。这个操作可以取出一个整数二进制表示中最低位的1及其后面的0。例如x12(1100b)lowbit 4(100b)。这在树状数组Fenwick Tree中是基础操作。统计1的个数Popcount内置函数__builtin_popcount(state)GCC/Clang。手动计算int countBits(int n) { int count 0; while (n) { n (n - 1); // 每次操作消去最低位的1 count; } return count; }4.3 状态压缩动态规划DP解法作为对DFS解法的补充我们来看一下DP解法。这能帮助我们更好地理解状态之间的转移关系。long long dp[1 10] {0}; // dp[state] 表示达到状态state的方案数 dp[0] 1; // 初始状态一个数都不选视为1种方案 // 对每个候选平方数已经过排序和去重 for (auto [sqVal mask] : squares) { // 倒序遍历所有状态这是01背包“每种物品只有一个”的思想 // 正序遍历会导致一个平方数被重复使用多次 for (int state FULL_STATE; state 0; --state) { // 如果当前状态state包含mask这个子集并且state-mask这个状态是可达的 if ((state mask) mask) { // 等价于 mask 是 state 的子集 dp[state] dp[state ^ mask]; // state ^ mask 就是从state中移除mask集合 } } } cout DP Answer: dp[FULL_STATE] endl;重要提示上面的DP代码存在重复计数问题因为它把{1 4}和{4 1}当成了两种方案。为了解决这个问题我们需要引入“顺序”的概念。一个经典的方法是使用“枚举子集”的技巧并配合平方数排序但实现起来比DFS复杂。这也是为什么DFS顺序剪枝在该问题上更受欢迎的原因。DP解法更通用的形式是“状态压缩DP枚举子集”其正确实现需要保证划分的无序性通常需要对平方数进行排序并在转移时增加限制或者使用另一种状态定义方式。5. 调试技巧与常见问题即便思路清晰在实现过程中也可能遇到各种“坑”。下面分享一些我在实现和调试这道题时总结的经验。5.1 问题一答案总是偏大这是最常见的问题几乎百分之百是因为方案去重没做好。症状运行程序得出的答案比标准答案大很多。诊断你的程序很可能把同一种数字划分方案因平方数加入顺序不同而重复计算了多次。例如全集{0123456789}被划分为{1 4} {9} {25} {36} {0} {784}。如果你的DFS允许先选9再选1或者先选1再选9最终都被计入那么方案数就会翻倍。解决确保在DFS中加入了顺序性剪枝即参数lastIdx。仔细检查递归调用dfs(nextState i)而不是dfs(nextState 0)或dfs(nextState lastIdx1)。i保证了后续选择的平方数索引不小于当前结合预处理排序就保证了数值非递减。5.2 问题二预处理时漏掉了平方数0症状答案比标准答案略小。诊断在getMask函数中while(num0)循环会直接跳过num0的情况导致平方数0没有被加入候选列表。而0是一个合法的平方数00*0并且它只使用数字0是许多有效方案的一部分。解决在getMask函数开头增加对num0的特殊判断直接返回1 0。5.3 问题三递归深度过深或运行超时症状程序运行缓慢甚至栈溢出。诊断虽然状态只有1024种但DFS的递归分支可能很多。如果预处理生成的候选平方数过多比如没有检查数字重复把121这样有重复数字的平方数也加进去了或者剪枝不够有效会导致递归树非常庞大。解决加强预处理过滤确保getMask函数正确过滤掉包含重复数字的平方数。验证剪枝确保if (curState mask) continue;这一行代码正确无误。使用迭代加深或DP如果递归确实太深可以考虑用栈模拟递归或者直接使用状态压缩DP的迭代写法。对于本题正确的DFS效率是极高的超时通常意味着代码有逻辑错误。5.4 一个实用的调试方法打印关键路径当答案不对时可以修改DFS函数让它打印出找到的合法方案这样能直观地看到重复或遗漏。vectorlong long path; // 记录当前路径上的平方数 void dfs_debug(int curState int lastIdx) { if (curState FULL_STATE) { for (auto val : path) cout val ; cout endl; ans; return; } for (int i lastIdx; i squares.size(); i) { // ... 判断条件 ... path.push_back(squares[i].first); dfs_debug(curState | squares[i].second i); path.pop_back(); // 回溯 } }通过观察打印出的方案序列你可以快速判断去重逻辑是否生效序列应该是非递减的以及是否包含了所有可能的平方数。6. 从这道题到更广阔的的应用“凑平方数”虽然是一道竞赛题但其蕴含的“状态压缩”思想具有极高的实用价值。它本质上解决了一类“集合划分”或“集合覆盖”问题这类问题在资源分配、任务调度、电路设计等领域都有出现。核心思想迁移当你遇到一个问题其状态可以用一个规模不大的集合通常元素数20因为2^20约等于100万是计算机可处理的范围来表示并且状态转移涉及集合的并、交、补运算时就应该立即想到状态压缩和位运算。举例旅行商问题TSP的经典DP解法用dp[mask][i]表示访问过城市集合mask最后停留在城市i的最短路径。mask就是一个状态压缩的整数。棋盘覆盖问题用二进制表示一行的格子状态如1表示已覆盖0表示未覆盖通过位运算判断上下行状态的兼容性。权限管理系统用不同的二进制位表示不同的操作权限如读、写、执行、删除。一个用户的权限集就是一个整数检查权限就是位与操作。掌握位运算不仅仅是学会了几种操作符更是掌握了一种高效建模复杂状态的思维方式。它让我们的程序能从繁琐的数组操作中解放出来直接操作“状态”这个整体既提升了效率也简化了逻辑。下次当你再遇到看似复杂的组合问题时不妨先想一想“我能不能用一个整数的二进制位来表示它”这或许就是打开高效解法之门的钥匙。