蓝桥杯凑平方数题解：位运算状态压缩与DFS搜索实战

1. 问题重述与核心难点剖析“凑平方数”这道题是2016年蓝桥杯国赛C B组的一道填空题。题目本身描述并不复杂给定0-9这十个数字每个数字恰好使用一次将它们排列成一个或多个整数要求这些整数都是完全平方数。题目问的是有多少种不同的凑法。初看之下很多人的第一反应是暴力搜索生成0-9的所有排列10! 3,628,800种然后尝试在数字串中插入分割点将数字串分割成若干个子串再检查每个子串对应的整数是否为完全平方数。这个思路直观但实现起来效率极低且逻辑复杂极易出错。关键在于如何高效地“枚举”所有可能的分割方案并快速判断一个数是否为完全平方数。这正是题目希望我们深入思考的地方——如何利用位运算来优雅地表示和遍历状态从而将指数级的枚举复杂度转化为在状态空间上的高效搜索。这道题的经典解法核心在于“状态压缩”思想。0-9这十个数字每个数字只有“已使用”和“未使用”两种状态。这天然地可以用一个10位的二进制数来表示我们称之为“状态字”或“掩码”mask。例如状态字0b0000000001十进制1表示只使用了数字00b1111111111十进制1023表示所有数字都已使用。这样我们搜索的过程就不再是笨拙地维护一个已使用数字的列表并进行查找而是通过二进制的位操作来高效地记录和转移状态。然而仅仅用状态压缩记录数字使用情况还不够。我们还需要枚举当前正在“构造”的这个平方数。一个更巧妙的思路是预先计算出所有由不同数字组成的完全平方数。因为最终拼凑用的每个整数其各位数字必然互异且来自0-9这个大集合。我们可以遍历一个足够大的范围比如0到99999的平方筛选出那些各位数字互不重复的数并将其数字组成也编码成一个状态字。这样我们的问题就转化为了从这些预处理的“平方数零件”中挑选若干个要求它们的状态字互不重叠即数字没有重复使用且最终所有状态字的“或”运算结果等于1023即0-9全部用完。这变成了一个在“零件库”中进行组合搜索的问题。2. 核心数据结构设计与预处理2.1 平方数的筛选与状态编码首先我们需要确定搜索的上界。题目由0-9组成最多是一个10位数。最大的10位数是9876543210它的平方根大约是99380。因此我们只需要遍历从0到100000取个整的平方数即可覆盖所有可能。对于每一个平方数num i*i我们需要做两件事检查其十进制表示中各位数字是否互不相同。如果满足条件1则将其数字集合编码为一个状态字mask同时记录这个平方数的值num。这里有一个关键细节数字0。平方数本身可能是0或者以0开头如012即12。在组合时以0开头的数是不合法的除非这个数就是0本身因为这不是一个标准的整数表示。例如“01”和“1”在数值上相等但占用了数字0和1而“1”只占用了数字1这会导致重复计数。因此在预处理时我们必须将数字转换为字符串检查其首位是否为‘0’且长度大于1。如果是则丢弃。让我们用C代码来演示这个预处理过程。我们将使用long long类型来存储平方数因为100000*100000仍在long long的表示范围内。#include iostream #include vector #include cmath #include algorithm using namespace std; typedef long long ll; vectorpairll, int squares; // 存储 (平方数值, 对应的状态掩码) // 检查一个数的各位数字是否互异并返回其状态掩码 int getMask(ll x) { if (x 0) return 1; // 数字0单独处理其掩码为1 (0b1) int mask 0; while (x 0) { int digit x % 10; int bit 1 digit; if (mask bit) return -1; // 数字重复返回-1表示无效 mask | bit; x / 10; } return mask; } void preprocess() { squares.clear(); squares.push_back(make_pair(0, 1)); // 预先加入0 for (ll i 1; i 100000; i) { ll num i * i; // 将数字转为字符串检查是否有前导0且不是单个0 string s to_string(num); if (s[0] 0 s.length() 1) continue; // 含有前导0的无效数 int mask getMask(num); if (mask ! -1) { squares.push_back(make_pair(num, mask)); } } // 可选按数值或掩码排序方便后续处理或去重但本题组合搜索对顺序不敏感 // sort(squares.begin(), squares.end()); }执行完preprocess()后squares向量中就存放了所有有效的“平方数零件”。每个零件是一个(数值 掩码)对。例如平方数49对应的掩码是(14) | (19)。2.2 状态搜索DFS与位运算的配合有了零件库接下来的问题就是组合搜索。我们需要从squares中选取若干个零件使得任意两个零件的掩码mask_i和mask_j满足(mask_i mask_j) 0数字无重复。所有被选零件的掩码进行“或”运算后结果等于FULL_MASK (110)-1 1023数字全部用完。这是一个典型的状态空间搜索问题。我们可以使用深度优先搜索DFS来遍历所有可能的组合。DFS函数的参数通常包括current_mask: 当前已使用的数字集合状态。start_index: 在squares数组中开始搜索的索引用于避免重复组合例如先选A再选B和先选B再选A被视为同一种组合。搜索的终止条件是current_mask FULL_MASK此时我们找到了一种合法的组合答案加1。但是直接这样搜索的复杂度仍然很高。squares数组的大小大约在几万量级对其进行子集枚举是不可行的。我们需要剪枝。关键剪枝策略顺序剪枝传入start_index参数保证我们总是从零件库的某个位置开始向后选取这样自然避免了(A,B)和(B,A)这种顺序不同但集合相同的重复。状态兼容性剪枝在尝试加入一个零件squares[i]时首先检查(current_mask squares[i].mask) 0。如果不为0说明有数字冲突直接跳过。状态预判剪枝可选但有效如果当前已选零件的掩码中已经包含了某个数字那么后续所有包含该数字的零件都可以被快速跳过。我们可以预先对squares数组进行分组或者使用更高级的数据结构如“舞蹈链”但对于本题规模前两种剪枝已经足够。下面给出DFS搜索的核心代码框架int FULL_MASK (1 10) - 1; // 0b1111111111 long long ans 0; // 结果可能很大用long long int n; // squares的大小 void dfs(int cur_mask, int start) { if (cur_mask FULL_MASK) { ans; return; } // 从start开始尝试加入新的平方数 for (int i start; i n; i) { int new_mask squares[i].second; if ((cur_mask new_mask) 0) { // 数字不冲突 dfs(cur_mask | new_mask, i 1); // 注意下一层start从i1开始 } // 这里可以添加更多剪枝例如如果剩余数字无法凑满可以提前退出 // 但需要额外的预处理来计算“从索引i开始所有零件掩码的并集”是否可能覆盖剩余数字。 // 对于本题不加此优化也能在可接受时间内完成。 } }在主函数中我们这样调用int main() { preprocess(); n squares.size(); ans 0; dfs(0, 0); // 初始状态掩码为0未使用任何数字从索引0开始搜索 cout ans endl; return 0; }3. 算法优化与去重深思运行上述代码你可能很快会得到一个答案。但这里存在一个巨大的陷阱重复计数。考虑这样一个组合我们选取了平方数1(掩码11)4(掩码14)9(掩码19)25(掩码(12)|(15))36(掩码(13)|(16))784(掩码(17)|(18)|(14)... 等等这里4和784都包含了数字4违反了规则。让我们换个正确的例子。问题在于我们搜索的是“零件的集合”。但是题目要求的是“将这些数字排列成一个或多个整数”。整数之间的顺序是不重要的。也就是说{1, 4, 9, 25, 36, 784}和{4, 1, 9, 25, 36, 784}是同一种凑法。我们的DFS通过start_index避免了集合内部的顺序问题。然而还有另一个层面的重复零件本身的数值重复但来自不同的平方根。例如平方数81可以由9*9得到。在预处理时我们只根据81这个数值和其数字掩码(18)|(11)存储了一次。这没问题。但是考虑数字0和1。它们可以组成01和1。01因为前导零被我们过滤掉了。那么1呢1 1*1 它会被加入零件库。0呢0 0*0也被加入。那么组合{0, 1}和组合{1}在使用数字上是一样的吗{0,1}使用了数字0和1掩码是(10)|(11)3。而{1}只使用了数字1掩码是2。这是两种不同的状态对应了两种不同的“凑”法一种是把0单独作为一个平方数另一种是把0和1拼成“10”或“01”不“01”无效“10”不是平方数。所以{0,1}意味着两个独立的平方数0和1。{1}意味着只有一个平方数1数字0没有被使用。这显然是不同的方案。那么重复究竟在哪考虑一个由多个一位数平方数组成的方案例如{0, 1, 4, 9}。这个方案对应的数字集合是{0,1,4,9}。但是{1, 4, 9, 0}是同一个集合。我们的DFS通过start_index保证了我们只会以(0,1,4,9)这个顺序来“构造”这个集合不会重复。看起来没问题。真正的坑在于我们的零件库squares中包含了所有可能的平方数包括那些本身就是其他平方数子集的数。例如49掩码包含4和9和4、9这两个零件。在搜索时我们可能会找到这样两条路径路径A选取了4和9两个零件。路径B选取了49这一个零件。 如果最终的数字集合都是{4,9}那么它们对应的是同一种“凑”法吗不是的路径A产生了两个整数4和9路径B产生了一个整数49。这是题目中明确不同的两种凑法因为题目要求的是“排列成一个或多个整数”整数49和整数4,9是不同的。所以这种“重复”是合法的不应该被去除。那么我们之前担心的重复到底是什么我们担心的是“集合”的重复但题目区分“整数”的划分。所以我们的算法在逻辑上是正确的。它会计数{4,9}和{49}为两种不同的方案。然而还有最后一个细节数字0作为平方数0。0是一个特殊的平方数。在我们的预处理中我们允许了单个数字0。那么组合{0, 1, 4, 9, 25, 36, 784}是合法的吗我们需要检查所有数字是否恰好用完。假设这个组合用掉了{0,1,2,3,4,5,6,7,8,9}那么它是合法的。但是如果有一个组合是{0, 1, 4, 9, 25, 36, 784, ...}它可能已经重复使用了某些数字比如4这在DFS的位运算检查中会被(cur_mask new_mask) 0过滤掉所以不会产生。所以最终的算法就是预处理所有无重复数字且无非法前导零的平方数包括0然后DFS搜索所有不冲突的组合当组合掩码等于1023时计数。4. 完整代码实现与结果验证将以上所有部分整合并添加一些细微的优化比如对squares按掩码的位数排序优先尝试数字多的零件可能有助于快速填满掩码起到一定的剪枝效果我们得到最终代码。#include iostream #include vector #include string #include algorithm using namespace std; typedef long long ll; vectorpairll, int sq; // 存储(平方数 掩码) int FULL_MASK (1 10) - 1; long long answer 0; // 获取数字掩码重复返回-1 int getMask(ll x) { if (x 0) return 1 0; // 数字0的掩码是1 int m 0; while (x) { int d x % 10; int b 1 d; if (m b) return -1; m | b; x / 10; } return m; } void preprocess() { sq.clear(); // 加入0 sq.push_back({0, 1 0}); for (ll i 1; i 100000; i) { ll num i * i; string s to_string(num); // 检查前导零长度大于1且首位为0 if (s.length() 1 s[0] 0) continue; int mask getMask(num); if (mask ! -1) { sq.push_back({num, mask}); } } // 按掩码的位数即数字个数降序排序是一种搜索顺序优化 sort(sq.begin(), sq.end(), [](const pairll, int a, const pairll, int b) { return __builtin_popcount(a.second) __builtin_popcount(b.second); }); } void dfs(int cur_mask, int start) { if (cur_mask FULL_MASK) { answer; return; } for (int i start; i (int)sq.size(); i) { int new_mask sq[i].second; if ((cur_mask new_mask) 0) { dfs(cur_mask | new_mask, i 1); } } } int main() { preprocess(); cout Total valid squares: sq.size() endl; answer 0; dfs(0, 0); cout Answer: answer endl; return 0; }注意__builtin_popcount是GCC/Clang编译器提供的内建函数用于计算一个整数二进制表示中1的个数。在MSVC下可以使用__popcnt或标准库bitset中的count()方法。这里使用它来对零件按包含数字多少排序让包含数字多的零件优先被尝试有助于更快地填满所有数字从而提前剪掉一些不可能的分支。这只是一种启发式优化不影响结果正确性。运行这段代码经过一段时间的计算在普通计算机上可能需要几秒到十几秒会输出最终答案。对于2016年蓝桥杯国赛的这道题最终答案是300。5. 位运算在此题中的精妙之处与扩展思考回顾整个解题过程位运算扮演了至关重要的角色其精妙之处体现在状态的高效压缩与表示用一个int类型的低10位完美表示了0-9这十个数字的使用情况。这使得状态存储、传递和比较的复杂度降至O(1)。集合运算的硬件加速判断数字是否重复 (cur_mask new_mask 0)、合并数字集合 (cur_mask | new_mask)、判断是否完成 (cur_mask FULL_MASK)这些操作在CPU层面都是极快的位操作指令远快于使用setint等容器进行查找和插入。为剪枝提供基础正是由于状态是简单的整数我们才能快速进行兼容性判断这是深度剪枝的前提。这道题可以看作是“状态压缩动态规划状压DP”或“状态压缩搜索”的一个经典入门例题。它向我们展示了当问题规模中有一个维度是“是否选择”这种二值状态且这个维度的大小在20左右时位运算状态压缩往往是破题的关键。扩展思考如果数字可以重复使用但总次数有限制呢状态就无法用简单的0/1表示了可能需要用三进制甚至更高进制的状态压缩或者使用更通用的记忆化搜索。如果不是0-9而是‘A’-‘Z’呢状态掩码的位数需要增加到26位依然可以用int32位或long long64位表示算法框架完全不变。如何输出所有具体的组合方案而不仅仅是计数在DFS中可以维护一个栈记录当前路径上选择的平方数值。当cur_mask FULL_MASK时将栈内序列输出或保存。注意这样结果会非常多需要大量存储空间。在实际编程竞赛中遇到此类“排列组合”、“子集枚举”、“状态覆盖”的问题首先要想到的就是数字范围是否适合用位运算压缩。一旦确定代码的效率和简洁性都会得到质的提升。这道“凑平方数”题堪称是训练位运算思维和状态压缩搜索的绝佳范例。它教会我们的不仅是技巧更是一种将复杂组合问题映射到二进制空间进行高效处理的思维方式。