尧图网站建设 
1. 项目概述一道经典的国赛真题这道“凑平方数”题是2016年第七届蓝桥杯国赛C B组的压轴难题之一。当年在考场上它难倒了不少选手原因不在于算法本身有多高深而在于它巧妙地将“搜索”与“位运算”这两个基础知识点结合并设置了一个非常精妙的“状态去重”环节。很多同学能想到用DFS深度优先搜索去枚举所有数字组合但往往卡在如何高效判断一个组合是否合法以及如何避免生成重复的平方数集合上。这正是本题的核心价值所在——它考察的不是你会不会某个冷门的算法模板而是你能否灵活运用基础工具尤其是位运算来解决一个复杂的、需要严密逻辑的实际问题。简单来说题目是这样的给定0-9这十个数字每个数字恰好使用一次你需要将它们排列成一个或多个整数使得每个整数都是完全平方数。例如数字集合{0,1,4,6,8,9}可以组成“81”和“6409”其中819²但6409不是平方数所以这个组合就不行。题目最终要求的是所有可能的组合方式总数。理解题意后你会发现它本质上是一个“集合划分”问题把0-9这个全集划分成若干个互不相交的子集每个子集能构成一个完全平方数。而解题的钥匙就藏在“位运算”之中。2. 核心思路拆解为什么是位运算面对这道题一个最直接的暴力想法是生成0-9的所有排列10! 3,628,800种然后尝试在每个排列中插入分割点将长串数字切分成多个数再逐个判断是否为平方数。这个思路的复杂度是灾难性的因为分割方案的数量是2的9次方量级在9个间隔中选择是否分割再乘上排列数完全不可行。因此我们必须转换思路。核心观察点是我们并不关心数字的具体排列顺序只关心哪些数字被用在了同一个平方数里。例如平方数81使用了数字8和1那么我们就可以用一个二进制数来代表这个数字集合。对于0-9我们可以用10位二进制数表示第i位为1表示数字i被包含在内。那么81对应的集合就是数字8和1二进制表示为(18) | (11)。这样一来整个问题的解决路径就清晰了可以分为三大步预处理所有合法的“平方数状态”遍历所有可能的完全平方数从0²到99²甚至更大但需注意位数检查它是否由不重复的0-9数字构成。如果是就计算它使用了哪些数字得到一个10位的状态码state并将这个状态码和对应的平方数值存储起来。这里要注意处理前导零的问题比如“01”是不合法的整数。状态搜索与组合我们现在有了一个合法的状态列表。问题转化为从这些状态中选出若干个状态要求它们两两之间没有重复的数字即状态码的按位与结果为0并且所有选中状态的按位或结果等于0-9的全集即(110)-1。我们需要找出所有满足条件的组合。高效去重这是本题最易错的地方。不同的状态组合可能对应同一组平方数集合只是顺序不同。例如状态A(代表81)和状态B(代表36)的组合与状态B和状态A的组合是同一个解。我们需要一种方法来避免重复计数。位运算的灵活性在这里发挥得淋漓尽致。步骤1中我们用位运算快速生成和检查状态步骤2中我们用位运算的与()、或(|)操作来高效判断状态间的互斥性和集合的完备性步骤3的去重更是需要巧妙的位运算技巧通常通过“状态码递增枚举”或“将找到的组合状态进行标准化排序”来实现。3. 预处理生成所有合法的平方数状态这是整个算法的基础务必做到准确无误。我们先确定平方数的范围。因为要用0-9不重复组成一个数这个数最大可能是9876543210它的平方根大约是99380。但我们实际上不需要遍历这么大。一个由不重复数字构成的数其位数最多10位。所以我们可以遍历所有不超过10位的完全平方数。更保守且高效的做法是遍历所有0-9数字组成的排列或直接遍历平方根计算其平方然后检查平方数是否合法。但在实现时更常见的做法是反向生成遍历平方根i计算i²然后判断i²是否由互不相同的数字组成且没有前导零问题。这里的前导零问题需要仔细处理例如i10, i²100数字为‘1’‘0’‘0’出现了重复的‘0’不合法i33, i²1089数字为‘1’‘0’‘8’‘9’全部不同合法。我们来看具体的C实现要点#include iostream #include vector #include cmath #include algorithm using namespace std; vectorpairlong long, int squares; // 存储 (平方数值, 状态码) void preprocess() { // 估算平方根上限最大的10位不重复数字是9876543210其平方根约为99380 // 但实际我们只需要遍历到其平方数不超过10位数即可这里取一个足够大的值100000 for (long long i 0; i 100000; i) { long long sq i * i; long long t sq; int state 0; // 10位状态码初始为0 bool valid true; // 处理数字0的特殊情况如果平方数就是0状态码为(10) if (t 0) { state | (1 0); squares.push_back({sq, state}); continue; } // 分解平方数的每一位数字 while (t 0) { int digit t % 10; if (state (1 digit)) { // 如果该数字位已经为1说明数字重复 valid false; break; } state | (1 digit); // 将对应位置1 t / 10; } if (valid) { // 还需要检查前导零实际上我们的分解方式(t0)已经自然处理了数字只要sq!0就不会有前导零被计入state。 // 例如104分解得到4,0,1状态码正确。但如果平方数本身是0我们已经单独处理。 squares.push_back({sq, state}); } } // 可选对squares按状态码或数值排序便于后续处理 // sort(squares.begin(), squares.end()); }注意这里有一个关键细节。我们判断数字是否重复是在生成状态码state的过程中进行的。state的每一位代表一个数字是否出现。如果sq是0它是一个特殊的合法平方数只包含数字0。我们必须单独处理因为while(t0)的循环不会执行。预处理完成后squares这个向量里就存放了所有可能的、由不重复数字构成的完全平方数及其对应的状态码。你可以打印一下看看数量通常不会超过1000个这比直接处理10!的排列要小得多。4. 深度搜索与位运算判重有了所有合法的平方数状态问题就变成了一个经典的“子集选取”问题。我们需要从squares中选出一个子集满足子集中所有元素的状态码两两互斥state_a state_b 0。所有选中状态码的按位或结果等于全量状态码FULL (110)-1。最直观的方法是深度优先搜索(DFS)。DFS的参数通常包括current_state: 当前已选状态码的按位或结果表示已经使用了哪些数字。start_index: 从squares的哪个位置开始尝试选择为了避免重复组合我们按顺序选取这是一种常见的去重技巧。搜索过程的核心代码框架如下long long FULL (1 10) - 1; // 二进制为1111111111表示0-9全部用完 int ans 0; // 最终答案计数 vectorint current_set; // 当前选中的状态码用于调试或输出具体方案 void dfs(int current_state, int start_idx) { if (current_state FULL) { // 找到一个合法组合 ans; // 可选打印current_set查看具体组合 return; } for (int i start_idx; i squares.size(); i) { int state squares[i].second; long long value squares[i].first; // 关键判断1当前状态码与已选状态码是否冲突 if (current_state state) { continue; // 有重复数字冲突 } // 关键判断2如果当前数字是0且state就是(10)需要特别小心吗 // 不需要它和其他不包含0的状态码自然互斥。 // 选择当前状态 current_set.push_back(value); dfs(current_state | state, i 1); // 注意下一层从i1开始避免重复选择同一元素和顺序重复 current_set.pop_back(); // 回溯 } }为什么start_idx参数能去重这是避免组合顺序重复的关键。我们规定在构造一个合法集合时只允许按照squares数组中的顺序“向后”选取。例如squares中有状态A(81)和状态B(36)。当我们搜索时只会考虑先选A再选B的路径i从A的索引开始下一层从B的索引开始。而先选B再选A的路径由于在选B时start_idx是B的索引下一层无法再回头选索引更小的A因此这条路径根本不会被生成。这样就保证了{A, B}这个集合只被计数一次。初始化调用dfs(0, 0)。从空状态开始从数组索引0开始尝试。这种搜索方式高效且优雅地解决了问题。但这里还有一个巨大的陷阱也是很多初学者甚至是一些老手容易忽略的地方。5. 关键陷阱与状态去重精讲上面的DFS代码看起来正确实际上却会得出错误的答案。问题出在哪里问题在于squares数组中可能存在多个不同的平方数但它们使用的数字集合即状态码是完全相同的考虑这个例子数字{1, 6, 9}可以组成平方数16913²、19614²和96131²。这三个平方数不同但它们的状态码一模一样都是(11) | (16) | (19)。在我们的DFS中它们被视为三个不同的“物品”。当我们搜索时可能会先选169再选其他状态也可能会先选196再选其他状态。这会导致我们最终统计的组合数虚高因为对于最终的“数字集合划分”来说{1,6,9}这个子集无论对应169、196还是961都只应算作同一种情况。所以我们必须进行状态码级别的去重。在预处理之后我们需要将squares数组中所有状态码相同的项合并或者更简单地说在DFS时对于状态码相同的平方数我们只应该考虑一次。解决方案有两种方案一预处理合并。在生成squares后使用一个mapint, vectorlong long将相同状态码的平方数值归类。在DFS时我们遍历的是不重复的状态码。当选中一个状态码时它背后可能对应多个平方数值如169,196,961这意味着在当前解中{1,6,9}这个位置有3种不同的“填充”方式。因此最终答案需要乘以这个状态码对应的平方数个数。这种方法逻辑清晰但计算组合数时需要做乘法稍微复杂。方案二搜索时跳过重复状态。这是更简洁高效的做法。我们对squares数组按照state进行排序。在DFS的循环中如果发现当前项的state和前一项的state相同我们就跳过它。因为对于相同的状态码我们只取第一个作为代表或者任意一个这样可以保证在搜索树上每个唯一的状态码只被枚举一次。修改后的预处理和DFS关键部分// 修改预处理将squares按照(state, value)排序方便去重 bool cmp(const pairlong long, int a, const pairlong long, int b) { if (a.second ! b.second) return a.second b.second; return a.first b.first; } void preprocess() { // ... 生成squares的代码同上 ... sort(squares.begin(), squares.end(), cmp); } void dfs(int current_state, int start_idx) { if (current_state FULL) { ans; return; } for (int i start_idx; i squares.size(); i) { int state squares[i].second; if (current_state state) continue; // **关键去重步骤**如果当前状态码和前一个状态码相同则跳过 if (i start_idx state squares[i-1].second) { continue; } dfs(current_state | state, i 1); // 注意这里不再需要回溯“值”因为我们只关心状态码的组合 } }实操心得这个“状态码去重”点是本题最核心的考察点也是区分选手是否思考透彻的关键。在竞赛中能写出DFS框架的选手不少但能意识到并正确处理这个隐藏重复条件的人才能拿到满分。一定要养成习惯当用状态压缩表示集合时时刻警惕多个不同元素映射到同一状态的情况。6. 完整代码实现与逐行解析结合以上所有分析我们给出完整的C解决方案并附上详细注释。#include iostream #include vector #include algorithm using namespace std; vectorpairlong long, int squares; // 存储平方数值 状态码 long long FULL (1 10) - 1; // 0-9全满的状态码 int ans 0; // 比较函数用于对squares排序优先按状态码其次按数值 bool cmp(const pairlong long, int a, const pairlong long, int b) { if (a.second ! b.second) return a.second b.second; return a.first b.first; } // 预处理函数生成所有由不重复数字构成的完全平方数 void preprocess() { // 平方根上限估算最大10位数是9876543210其平方根约99380这里取100000足够 for (long long i 0; i 100000; i) { long long sq i * i; long long t sq; int state 0; bool valid true; // 单独处理平方数为0的情况 if (t 0) { squares.push_back({0, 1 0}); // 状态码只有第0位为1 continue; } // 分解平方数的每一位并检查数字是否重复 while (t 0) { int digit t % 10; if (state (1 digit)) { // 该数字已出现重复 valid false; break; } state | (1 digit); // 标记该数字已出现 t / 10; } if (valid) { squares.push_back({sq, state}); } } // 排序便于DFS时进行状态码去重 sort(squares.begin(), squares.end(), cmp); // 调试可以打印出所有合法的平方数和状态码 // for (auto p : squares) { // cout Value: p.first , State: bitset10(p.second) endl; // } // cout Total valid squares: squares.size() endl; } // 深度优先搜索核心函数 // current_state: 当前已使用的数字集合状态码 // start_idx: 从squares数组的哪个索引开始尝试避免顺序重复 void dfs(int current_state, int start_idx) { // 终止条件所有0-9数字都已使用 if (current_state FULL) { ans; return; } // 从start_idx开始遍历所有平方数状态 for (int i start_idx; i squares.size(); i) { int state squares[i].second; // 剪枝1如果当前状态码与已选状态有重叠数字则跳过 if (current_state state) { continue; } // 剪枝2关键去重如果当前状态码与前一个状态码相同则跳过。 // 因为排序后相同状态码相邻我们只取第一个。 // i start_idx 确保是在同一层递归中比较而不是和上一层的选择比较。 if (i start_idx state squares[i-1].second) { continue; } // 选择当前状态继续深入搜索 dfs(current_state | state, i 1); // 无需显式回溯current_state因为参数是值传递递归返回自动恢复 } } int main() { preprocess(); // 步骤1预处理所有合法平方数状态 ans 0; dfs(0, 0); // 步骤2从空状态开始深度搜索 cout Total number of combinations: ans endl; return 0; }代码逐行解析与关键点数据结构使用vectorpairlong long, int squares存储first是平方数值second是10位状态码。用int存储状态码足够因为2^101024。预处理循环i的上限取100000是保守且安全的确保覆盖所有可能的不超过10位的平方数。在循环内部通过while(t0)逐位分解并检查重复。state的每一位对应一个数字是否出现。排序sort(squares.begin(), squares.end(), cmp)首先按状态码(second)升序排序状态码相同的再按平方数值(first)排序。这为DFS中的去重判断state squares[i-1].second提供了基础。DFS函数dfs参数current_state是当前累积状态码start_idx是搜索起点索引。使用start_idx保证了我们选出的状态码组合是递增索引的从而避免了{A,B}和{B,A}这种顺序重复。终止条件current_state FULL即所有数字(0-9)都被用到。循环内的第一个if(current_state state)进行按位与操作结果非0说明有重复数字剪枝。循环内的第二个if去重核心if (i start_idx state squares[i-1].second)。i start_idx确保是在同一层递归的循环内进行比较。如果当前状态码和前一个状态码相同则跳过。这保证了对于同一组数字集合如{1,6,9}无论它对应169、196还是961在搜索树中只被作为一个分支展开一次。递归调用dfs(current_state | state, i 1)。current_state | state将新状态合并i 1确保下一层从当前元素之后开始选择这是组合问题避免重复的经典写法。主函数依次调用preprocess()和dfs(0,0)最后输出结果ans。运行这段代码最终输出的答案就是本题的正确解。7. 性能分析与优化探讨虽然上述解法已经足够通过竞赛评测但我们还是可以深入分析一下其性能并探讨可能的优化方向这对于理解算法竞赛的思维模式很有帮助。时间复杂度分析预处理阶段循环约10^5次每次循环进行常数次的位运算和整数操作复杂度为O(10^5)完全可以接受。搜索阶段这是主要开销。squares数组的大小M经过状态去重后是关键。经过实际运行合法的、状态码不重复的平方数大约有600多个。DFS需要遍历这些状态的所有组合。最坏情况下我们需要枚举所有子集复杂度是O(2^M)这看起来是天文数字。但得益于两个强有力的剪枝互斥剪枝只有当新状态与当前状态不冲突时才继续搜索。这极大地减少了搜索树的分支。顺序剪枝通过start_idx我们实际上枚举的是组合而非排列搜索树大小从M!量级降为C(M, k)的组合和。 实际运行时DFS的递归调用次数远小于2^M。在普通PC上该程序能在毫秒级完成计算。空间复杂度分析主要空间用于存储squares向量大小约几千个元素每个元素是一个pairlong long, int空间消耗极小。进一步优化思路状态预过滤在预处理时可以提前排除一些明显不可能与其他状态组合成全集的“大状态”。例如如果一个平方数使用了超过5个数字那么剩下的数字很难再组成多个平方数来凑满10个。但这不是必须的因为DFS剪枝已经很有效。迭代加深搜索(IDDFS)或Meet-in-the-Middle理论上我们可以将10个数字分成两半分别枚举所有可能的状态组合然后再合并。但本题状态空间本身不大且DFS实现简单这些更复杂的优化带来的收益有限且增加了代码复杂度。使用位运算加速状态判断我们的代码已经大量使用了位运算。还可以考虑使用__builtin_popcount(state)来快速获取状态中1的个数即使用了几个数字用于启发式搜索或额外剪枝例如如果当前已用数字剩余最大可能数字 10可以提前剪枝。但同样对于本题数据规模并非必要。避坑技巧在竞赛中遇到此类状态压缩搜索的问题先写出清晰正确的暴力搜索框架再逐步加入剪枝和优化是更稳妥的策略。不要一开始就追求极致的优化导致代码复杂易错。本题的“状态码去重”就是一个典型的、必须先保证正确性才能谈优化的环节。8. 常见错误与调试记录在实现和教学过程中我总结了几类常见的错误供大家对照检查忽略数字0的单独处理在预处理判断平方数是否由不重复数字构成时如果平方数就是0while(t0)循环不会执行state保持为0。这会导致0这个合法的平方数被漏掉。必须在循环前单独判断if(t0)。状态码去重逻辑错误这是最普遍的错误。错误做法包括完全没有去重导致答案远大于标准答案。去重代码写错位置例如写在if (current_state state) continue;之前可能导致漏解。去重判断条件写错如if (i0 state squares[i-1].second)。这会导致在每一层递归中只要遇到和全局数组前一个相同的状态就跳过这是错误的。正确的应该是和本轮循环的起始索引进行比较即i start_idx。DFS参数传递与回溯错误错误地使用全局变量或引用传递current_state导致回溯时状态混乱。正确的做法是使用值传递(current_state | state)这样每一层递归都有自己的状态副本。start_idx参数传递错误。下一层应该是i1而不是start_idx1或i。i1保证了不会重复选择已选过的元素也保证了组合的无序性。整数溢出平方数i*i可能超出int范围因此i和sq应使用long long类型。调试建议首先编写一个printState函数将状态码整数转换为包含的数字集合字符串便于调试时查看。其次在DFS中找到解时(current_state FULL)不要仅仅计数可以打印出current_set存储了选择的平方数值验证每个解是否确实由不重复的0-9数字组成且每个数都是平方数。从小规模数据开始测试。例如可以先尝试只用数字0-4看看程序是否能正确找出所有组合。修改FULL为(15)-1并调整预处理中平方根的范围。这道“凑平方数”题堪称蓝桥杯国赛级别的经典。它不追求高深的算法而是深度考察选手对基础数据结构状态压缩、基础算法深度优先搜索的灵活运用能力以及对问题本质的洞察力状态去重。通过这道题我们能够深刻体会到位运算不仅是提速的工具更是一种强大的、用于表示和操作集合的思维模型。掌握这种思维对于解决许多复杂的组合问题、状态规划问题都大有裨益。在平时练习中多思考如何将问题抽象为集合操作如何用位运算简洁地表达约束条件是提升竞赛能力的重要途径。 蓝桥杯国赛真题解析：巧用位运算与DFS解决凑平方数问题
1. 项目概述一道经典的国赛真题这道“凑平方数”题是2016年第七届蓝桥杯国赛C B组的压轴难题之一。当年在考场上它难倒了不少选手原因不在于算法本身有多高深而在于它巧妙地将“搜索”与“位运算”这两个基础知识点结合并设置了一个非常精妙的“状态去重”环节。很多同学能想到用DFS深度优先搜索去枚举所有数字组合但往往卡在如何高效判断一个组合是否合法以及如何避免生成重复的平方数集合上。这正是本题的核心价值所在——它考察的不是你会不会某个冷门的算法模板而是你能否灵活运用基础工具尤其是位运算来解决一个复杂的、需要严密逻辑的实际问题。简单来说题目是这样的给定0-9这十个数字每个数字恰好使用一次你需要将它们排列成一个或多个整数使得每个整数都是完全平方数。例如数字集合{0,1,4,6,8,9}可以组成“81”和“6409”其中819²但6409不是平方数所以这个组合就不行。题目最终要求的是所有可能的组合方式总数。理解题意后你会发现它本质上是一个“集合划分”问题把0-9这个全集划分成若干个互不相交的子集每个子集能构成一个完全平方数。而解题的钥匙就藏在“位运算”之中。2. 核心思路拆解为什么是位运算面对这道题一个最直接的暴力想法是生成0-9的所有排列10! 3,628,800种然后尝试在每个排列中插入分割点将长串数字切分成多个数再逐个判断是否为平方数。这个思路的复杂度是灾难性的因为分割方案的数量是2的9次方量级在9个间隔中选择是否分割再乘上排列数完全不可行。因此我们必须转换思路。核心观察点是我们并不关心数字的具体排列顺序只关心哪些数字被用在了同一个平方数里。例如平方数81使用了数字8和1那么我们就可以用一个二进制数来代表这个数字集合。对于0-9我们可以用10位二进制数表示第i位为1表示数字i被包含在内。那么81对应的集合就是数字8和1二进制表示为(18) | (11)。这样一来整个问题的解决路径就清晰了可以分为三大步预处理所有合法的“平方数状态”遍历所有可能的完全平方数从0²到99²甚至更大但需注意位数检查它是否由不重复的0-9数字构成。如果是就计算它使用了哪些数字得到一个10位的状态码state并将这个状态码和对应的平方数值存储起来。这里要注意处理前导零的问题比如“01”是不合法的整数。状态搜索与组合我们现在有了一个合法的状态列表。问题转化为从这些状态中选出若干个状态要求它们两两之间没有重复的数字即状态码的按位与结果为0并且所有选中状态的按位或结果等于0-9的全集即(110)-1。我们需要找出所有满足条件的组合。高效去重这是本题最易错的地方。不同的状态组合可能对应同一组平方数集合只是顺序不同。例如状态A(代表81)和状态B(代表36)的组合与状态B和状态A的组合是同一个解。我们需要一种方法来避免重复计数。位运算的灵活性在这里发挥得淋漓尽致。步骤1中我们用位运算快速生成和检查状态步骤2中我们用位运算的与()、或(|)操作来高效判断状态间的互斥性和集合的完备性步骤3的去重更是需要巧妙的位运算技巧通常通过“状态码递增枚举”或“将找到的组合状态进行标准化排序”来实现。3. 预处理生成所有合法的平方数状态这是整个算法的基础务必做到准确无误。我们先确定平方数的范围。因为要用0-9不重复组成一个数这个数最大可能是9876543210它的平方根大约是99380。但我们实际上不需要遍历这么大。一个由不重复数字构成的数其位数最多10位。所以我们可以遍历所有不超过10位的完全平方数。更保守且高效的做法是遍历所有0-9数字组成的排列或直接遍历平方根计算其平方然后检查平方数是否合法。但在实现时更常见的做法是反向生成遍历平方根i计算i²然后判断i²是否由互不相同的数字组成且没有前导零问题。这里的前导零问题需要仔细处理例如i10, i²100数字为‘1’‘0’‘0’出现了重复的‘0’不合法i33, i²1089数字为‘1’‘0’‘8’‘9’全部不同合法。我们来看具体的C实现要点#include iostream #include vector #include cmath #include algorithm using namespace std; vectorpairlong long, int squares; // 存储 (平方数值, 状态码) void preprocess() { // 估算平方根上限最大的10位不重复数字是9876543210其平方根约为99380 // 但实际我们只需要遍历到其平方数不超过10位数即可这里取一个足够大的值100000 for (long long i 0; i 100000; i) { long long sq i * i; long long t sq; int state 0; // 10位状态码初始为0 bool valid true; // 处理数字0的特殊情况如果平方数就是0状态码为(10) if (t 0) { state | (1 0); squares.push_back({sq, state}); continue; } // 分解平方数的每一位数字 while (t 0) { int digit t % 10; if (state (1 digit)) { // 如果该数字位已经为1说明数字重复 valid false; break; } state | (1 digit); // 将对应位置1 t / 10; } if (valid) { // 还需要检查前导零实际上我们的分解方式(t0)已经自然处理了数字只要sq!0就不会有前导零被计入state。 // 例如104分解得到4,0,1状态码正确。但如果平方数本身是0我们已经单独处理。 squares.push_back({sq, state}); } } // 可选对squares按状态码或数值排序便于后续处理 // sort(squares.begin(), squares.end()); }注意这里有一个关键细节。我们判断数字是否重复是在生成状态码state的过程中进行的。state的每一位代表一个数字是否出现。如果sq是0它是一个特殊的合法平方数只包含数字0。我们必须单独处理因为while(t0)的循环不会执行。预处理完成后squares这个向量里就存放了所有可能的、由不重复数字构成的完全平方数及其对应的状态码。你可以打印一下看看数量通常不会超过1000个这比直接处理10!的排列要小得多。4. 深度搜索与位运算判重有了所有合法的平方数状态问题就变成了一个经典的“子集选取”问题。我们需要从squares中选出一个子集满足子集中所有元素的状态码两两互斥state_a state_b 0。所有选中状态码的按位或结果等于全量状态码FULL (110)-1。最直观的方法是深度优先搜索(DFS)。DFS的参数通常包括current_state: 当前已选状态码的按位或结果表示已经使用了哪些数字。start_index: 从squares的哪个位置开始尝试选择为了避免重复组合我们按顺序选取这是一种常见的去重技巧。搜索过程的核心代码框架如下long long FULL (1 10) - 1; // 二进制为1111111111表示0-9全部用完 int ans 0; // 最终答案计数 vectorint current_set; // 当前选中的状态码用于调试或输出具体方案 void dfs(int current_state, int start_idx) { if (current_state FULL) { // 找到一个合法组合 ans; // 可选打印current_set查看具体组合 return; } for (int i start_idx; i squares.size(); i) { int state squares[i].second; long long value squares[i].first; // 关键判断1当前状态码与已选状态码是否冲突 if (current_state state) { continue; // 有重复数字冲突 } // 关键判断2如果当前数字是0且state就是(10)需要特别小心吗 // 不需要它和其他不包含0的状态码自然互斥。 // 选择当前状态 current_set.push_back(value); dfs(current_state | state, i 1); // 注意下一层从i1开始避免重复选择同一元素和顺序重复 current_set.pop_back(); // 回溯 } }为什么start_idx参数能去重这是避免组合顺序重复的关键。我们规定在构造一个合法集合时只允许按照squares数组中的顺序“向后”选取。例如squares中有状态A(81)和状态B(36)。当我们搜索时只会考虑先选A再选B的路径i从A的索引开始下一层从B的索引开始。而先选B再选A的路径由于在选B时start_idx是B的索引下一层无法再回头选索引更小的A因此这条路径根本不会被生成。这样就保证了{A, B}这个集合只被计数一次。初始化调用dfs(0, 0)。从空状态开始从数组索引0开始尝试。这种搜索方式高效且优雅地解决了问题。但这里还有一个巨大的陷阱也是很多初学者甚至是一些老手容易忽略的地方。5. 关键陷阱与状态去重精讲上面的DFS代码看起来正确实际上却会得出错误的答案。问题出在哪里问题在于squares数组中可能存在多个不同的平方数但它们使用的数字集合即状态码是完全相同的考虑这个例子数字{1, 6, 9}可以组成平方数16913²、19614²和96131²。这三个平方数不同但它们的状态码一模一样都是(11) | (16) | (19)。在我们的DFS中它们被视为三个不同的“物品”。当我们搜索时可能会先选169再选其他状态也可能会先选196再选其他状态。这会导致我们最终统计的组合数虚高因为对于最终的“数字集合划分”来说{1,6,9}这个子集无论对应169、196还是961都只应算作同一种情况。所以我们必须进行状态码级别的去重。在预处理之后我们需要将squares数组中所有状态码相同的项合并或者更简单地说在DFS时对于状态码相同的平方数我们只应该考虑一次。解决方案有两种方案一预处理合并。在生成squares后使用一个mapint, vectorlong long将相同状态码的平方数值归类。在DFS时我们遍历的是不重复的状态码。当选中一个状态码时它背后可能对应多个平方数值如169,196,961这意味着在当前解中{1,6,9}这个位置有3种不同的“填充”方式。因此最终答案需要乘以这个状态码对应的平方数个数。这种方法逻辑清晰但计算组合数时需要做乘法稍微复杂。方案二搜索时跳过重复状态。这是更简洁高效的做法。我们对squares数组按照state进行排序。在DFS的循环中如果发现当前项的state和前一项的state相同我们就跳过它。因为对于相同的状态码我们只取第一个作为代表或者任意一个这样可以保证在搜索树上每个唯一的状态码只被枚举一次。修改后的预处理和DFS关键部分// 修改预处理将squares按照(state, value)排序方便去重 bool cmp(const pairlong long, int a, const pairlong long, int b) { if (a.second ! b.second) return a.second b.second; return a.first b.first; } void preprocess() { // ... 生成squares的代码同上 ... sort(squares.begin(), squares.end(), cmp); } void dfs(int current_state, int start_idx) { if (current_state FULL) { ans; return; } for (int i start_idx; i squares.size(); i) { int state squares[i].second; if (current_state state) continue; // **关键去重步骤**如果当前状态码和前一个状态码相同则跳过 if (i start_idx state squares[i-1].second) { continue; } dfs(current_state | state, i 1); // 注意这里不再需要回溯“值”因为我们只关心状态码的组合 } }实操心得这个“状态码去重”点是本题最核心的考察点也是区分选手是否思考透彻的关键。在竞赛中能写出DFS框架的选手不少但能意识到并正确处理这个隐藏重复条件的人才能拿到满分。一定要养成习惯当用状态压缩表示集合时时刻警惕多个不同元素映射到同一状态的情况。6. 完整代码实现与逐行解析结合以上所有分析我们给出完整的C解决方案并附上详细注释。#include iostream #include vector #include algorithm using namespace std; vectorpairlong long, int squares; // 存储平方数值 状态码 long long FULL (1 10) - 1; // 0-9全满的状态码 int ans 0; // 比较函数用于对squares排序优先按状态码其次按数值 bool cmp(const pairlong long, int a, const pairlong long, int b) { if (a.second ! b.second) return a.second b.second; return a.first b.first; } // 预处理函数生成所有由不重复数字构成的完全平方数 void preprocess() { // 平方根上限估算最大10位数是9876543210其平方根约99380这里取100000足够 for (long long i 0; i 100000; i) { long long sq i * i; long long t sq; int state 0; bool valid true; // 单独处理平方数为0的情况 if (t 0) { squares.push_back({0, 1 0}); // 状态码只有第0位为1 continue; } // 分解平方数的每一位并检查数字是否重复 while (t 0) { int digit t % 10; if (state (1 digit)) { // 该数字已出现重复 valid false; break; } state | (1 digit); // 标记该数字已出现 t / 10; } if (valid) { squares.push_back({sq, state}); } } // 排序便于DFS时进行状态码去重 sort(squares.begin(), squares.end(), cmp); // 调试可以打印出所有合法的平方数和状态码 // for (auto p : squares) { // cout Value: p.first , State: bitset10(p.second) endl; // } // cout Total valid squares: squares.size() endl; } // 深度优先搜索核心函数 // current_state: 当前已使用的数字集合状态码 // start_idx: 从squares数组的哪个索引开始尝试避免顺序重复 void dfs(int current_state, int start_idx) { // 终止条件所有0-9数字都已使用 if (current_state FULL) { ans; return; } // 从start_idx开始遍历所有平方数状态 for (int i start_idx; i squares.size(); i) { int state squares[i].second; // 剪枝1如果当前状态码与已选状态有重叠数字则跳过 if (current_state state) { continue; } // 剪枝2关键去重如果当前状态码与前一个状态码相同则跳过。 // 因为排序后相同状态码相邻我们只取第一个。 // i start_idx 确保是在同一层递归中比较而不是和上一层的选择比较。 if (i start_idx state squares[i-1].second) { continue; } // 选择当前状态继续深入搜索 dfs(current_state | state, i 1); // 无需显式回溯current_state因为参数是值传递递归返回自动恢复 } } int main() { preprocess(); // 步骤1预处理所有合法平方数状态 ans 0; dfs(0, 0); // 步骤2从空状态开始深度搜索 cout Total number of combinations: ans endl; return 0; }代码逐行解析与关键点数据结构使用vectorpairlong long, int squares存储first是平方数值second是10位状态码。用int存储状态码足够因为2^101024。预处理循环i的上限取100000是保守且安全的确保覆盖所有可能的不超过10位的平方数。在循环内部通过while(t0)逐位分解并检查重复。state的每一位对应一个数字是否出现。排序sort(squares.begin(), squares.end(), cmp)首先按状态码(second)升序排序状态码相同的再按平方数值(first)排序。这为DFS中的去重判断state squares[i-1].second提供了基础。DFS函数dfs参数current_state是当前累积状态码start_idx是搜索起点索引。使用start_idx保证了我们选出的状态码组合是递增索引的从而避免了{A,B}和{B,A}这种顺序重复。终止条件current_state FULL即所有数字(0-9)都被用到。循环内的第一个if(current_state state)进行按位与操作结果非0说明有重复数字剪枝。循环内的第二个if去重核心if (i start_idx state squares[i-1].second)。i start_idx确保是在同一层递归的循环内进行比较。如果当前状态码和前一个状态码相同则跳过。这保证了对于同一组数字集合如{1,6,9}无论它对应169、196还是961在搜索树中只被作为一个分支展开一次。递归调用dfs(current_state | state, i 1)。current_state | state将新状态合并i 1确保下一层从当前元素之后开始选择这是组合问题避免重复的经典写法。主函数依次调用preprocess()和dfs(0,0)最后输出结果ans。运行这段代码最终输出的答案就是本题的正确解。7. 性能分析与优化探讨虽然上述解法已经足够通过竞赛评测但我们还是可以深入分析一下其性能并探讨可能的优化方向这对于理解算法竞赛的思维模式很有帮助。时间复杂度分析预处理阶段循环约10^5次每次循环进行常数次的位运算和整数操作复杂度为O(10^5)完全可以接受。搜索阶段这是主要开销。squares数组的大小M经过状态去重后是关键。经过实际运行合法的、状态码不重复的平方数大约有600多个。DFS需要遍历这些状态的所有组合。最坏情况下我们需要枚举所有子集复杂度是O(2^M)这看起来是天文数字。但得益于两个强有力的剪枝互斥剪枝只有当新状态与当前状态不冲突时才继续搜索。这极大地减少了搜索树的分支。顺序剪枝通过start_idx我们实际上枚举的是组合而非排列搜索树大小从M!量级降为C(M, k)的组合和。 实际运行时DFS的递归调用次数远小于2^M。在普通PC上该程序能在毫秒级完成计算。空间复杂度分析主要空间用于存储squares向量大小约几千个元素每个元素是一个pairlong long, int空间消耗极小。进一步优化思路状态预过滤在预处理时可以提前排除一些明显不可能与其他状态组合成全集的“大状态”。例如如果一个平方数使用了超过5个数字那么剩下的数字很难再组成多个平方数来凑满10个。但这不是必须的因为DFS剪枝已经很有效。迭代加深搜索(IDDFS)或Meet-in-the-Middle理论上我们可以将10个数字分成两半分别枚举所有可能的状态组合然后再合并。但本题状态空间本身不大且DFS实现简单这些更复杂的优化带来的收益有限且增加了代码复杂度。使用位运算加速状态判断我们的代码已经大量使用了位运算。还可以考虑使用__builtin_popcount(state)来快速获取状态中1的个数即使用了几个数字用于启发式搜索或额外剪枝例如如果当前已用数字剩余最大可能数字 10可以提前剪枝。但同样对于本题数据规模并非必要。避坑技巧在竞赛中遇到此类状态压缩搜索的问题先写出清晰正确的暴力搜索框架再逐步加入剪枝和优化是更稳妥的策略。不要一开始就追求极致的优化导致代码复杂易错。本题的“状态码去重”就是一个典型的、必须先保证正确性才能谈优化的环节。8. 常见错误与调试记录在实现和教学过程中我总结了几类常见的错误供大家对照检查忽略数字0的单独处理在预处理判断平方数是否由不重复数字构成时如果平方数就是0while(t0)循环不会执行state保持为0。这会导致0这个合法的平方数被漏掉。必须在循环前单独判断if(t0)。状态码去重逻辑错误这是最普遍的错误。错误做法包括完全没有去重导致答案远大于标准答案。去重代码写错位置例如写在if (current_state state) continue;之前可能导致漏解。去重判断条件写错如if (i0 state squares[i-1].second)。这会导致在每一层递归中只要遇到和全局数组前一个相同的状态就跳过这是错误的。正确的应该是和本轮循环的起始索引进行比较即i start_idx。DFS参数传递与回溯错误错误地使用全局变量或引用传递current_state导致回溯时状态混乱。正确的做法是使用值传递(current_state | state)这样每一层递归都有自己的状态副本。start_idx参数传递错误。下一层应该是i1而不是start_idx1或i。i1保证了不会重复选择已选过的元素也保证了组合的无序性。整数溢出平方数i*i可能超出int范围因此i和sq应使用long long类型。调试建议首先编写一个printState函数将状态码整数转换为包含的数字集合字符串便于调试时查看。其次在DFS中找到解时(current_state FULL)不要仅仅计数可以打印出current_set存储了选择的平方数值验证每个解是否确实由不重复的0-9数字组成且每个数都是平方数。从小规模数据开始测试。例如可以先尝试只用数字0-4看看程序是否能正确找出所有组合。修改FULL为(15)-1并调整预处理中平方根的范围。这道“凑平方数”题堪称蓝桥杯国赛级别的经典。它不追求高深的算法而是深度考察选手对基础数据结构状态压缩、基础算法深度优先搜索的灵活运用能力以及对问题本质的洞察力状态去重。通过这道题我们能够深刻体会到位运算不仅是提速的工具更是一种强大的、用于表示和操作集合的思维模型。掌握这种思维对于解决许多复杂的组合问题、状态规划问题都大有裨益。在平时练习中多思考如何将问题抽象为集合操作如何用位运算简洁地表达约束条件是提升竞赛能力的重要途径。