1. 从一道竞赛题看算法优化的本质四平方和定理是数论里一个很经典的结论任何一个正整数都能表示成四个整数的平方和。这个结论早在几百年前就被拉格朗日证明过了但把它搬进编程竞赛里就变成了另一回事——不是让你证明存在性而是让你在有限时间内找到那组解还得是最优的那组。2016年蓝桥杯C A组出了这么一道题题目大意是给定一个正整数N求把它表示为四个非负整数平方和的所有方案中按a、b、c、d字典序最小的那一组。N的范围大概在5×10^6以内。看起来很简单对吧四层循环暴力枚举写完收工。但真在赛场上这么干的人大概率会超时。这道题真正考察的不是你会不会写循环而是你懂不懂得在暴力基础上做降维打击。我后来拿这道题给不少人练手发现一个很有意思的现象刚学C的人第一反应是四层for学过一点算法的人会想到三层for加二分而真正做过这类题的人会直接往哈希表或者两数平方和预处理的方向走。不同的思路代码量可能差不多但运行效率差了不止一个数量级。这篇文章我会把这道题从最朴素的暴力解法一路拆到最优方案每一步都讲清楚为什么这么改、改完能快多少、边界条件怎么处理。如果你正在准备蓝桥杯或者类似的算法竞赛这道题值得你花时间吃透——它涉及到的空间换时间、枚举降维、哈希预处理这几个技巧在后面的题目里会反复出现。2. 题目核心需求与暴力解法的局限2.1 题目到底在求什么先把问题形式化一下。给定正整数N要找四个非负整数a、b、c、d满足a² b² c² d² N并且要求(a, b, c, d)这个四元组在字典序下最小。所谓字典序最小就是先比aa小的优先a相同比bb小的优先以此类推。这里有个容易踩的坑题目要求的是非负整数不是正整数。也就是说0是允许的。很多人写循环的时候下意识从1开始枚举结果样例里带0的情况全挂了。这个细节看起来不起眼但赛场上因为这种边界丢分的人不在少数。另外字典序最小这个条件意味着我们不能随便找到一组就输出。比如N5方案有(0,0,1,2)和(1,1,1,1)等等但字典序最小的是(0,0,1,2)因为a0比a1小。所以我们的枚举策略必须保证第一次找到的解就是字典序最小的。2.2 朴素四重循环为什么不行最直接的写法是这样的for (int a 0; a * a N; a) for (int b a; b * b a * a N; b) for (int c b; c * c b * b a * a N; c) for (int d c; d * d c * c b * b a * a N; d) if (a*a b*b c*c d*d N) { cout a b c d; return 0; }这段代码逻辑上没问题而且因为是从小到大枚举第一次找到的解天然就是字典序最小的。但问题在于时间复杂度。当N5×10^6时a的取值范围大约是0到2236b、c、d也各有上千种可能。四层嵌套下来最坏情况的计算量是O(N²)级别的具体来说大约是N²/常数对于5×10^6的输入这个数字轻松突破10^10次运算。就算编译器再优化一秒之内也跑不完。有人可能会想加个剪枝不就行了每层循环都判断当前平方和是否已经超过N超过就break。这个剪枝确实有用能把实际运算量压下来不少但本质上还是O(N²)的复杂度面对极限数据依然吃力。我实测过在普通笔记本上跑N5×10^6的输入加了剪枝的四重循环大概需要十几秒才能出结果而竞赛的时间限制通常是1秒。2.3 关键洞察把四层降到两层这道题的核心突破口在于一个简单的数学变换。我们把等式重新排列一下a² b² N - c² - d²左边是a和b的平方和右边是N减去c和d的平方和。如果我们预先把所有可能的(a, b)组合及其平方和存起来那么对于每一组(c, d)只需要查表看是否存在对应的(a, b)使得两边相等就行了。这样一来原本的四层循环就被拆成了两个两层循环一层用来预处理(a, b)的平方和另一层用来枚举(c, d)并查表。时间复杂度从O(N²)直接降到了O(N)。对于N5×10^6O(N)的算法跑起来就是毫秒级别的完全不用担心超时。但这里有个新的问题怎么保证字典序最小因为我们把a、b和c、d分开处理了枚举顺序就变得很关键。这个我后面会详细讲先记住一个原则——预处理阶段要保证对于每个平方和存储的是字典序最小的那组(a, b)。3. 从O(N²)到O(N)哈希表方案的完整实现3.1 数据结构的选择要把(a, b)的平方和存起来并支持快速查询最自然的选择是哈希表。C里可以用unordered_mapint, pairint,int键是平方和值是对应的(a, b)组合。但这里有个细节需要注意同一个平方和可能对应多组(a, b)。比如25可以写成0²5²也可以写成3²4²。按照字典序最小的要求我们应该保留a最小的那组如果a相同则保留b最小的。由于我们枚举a和b的时候是从小到大的所以先存入哈希表的组合天然就是字典序最小的后面遇到相同的平方和直接跳过即可。unordered_mapint, pairint,int table; for (int a 0; a * a N; a) { for (int b a; b * b a * a N; b) { int sum a * a b * b; if (table.find(sum) table.end()) { table[sum] {a, b}; } } }注意内层循环从b a开始而不是从0开始。这是因为我们要求a ≤ b ≤ c ≤ d吗其实题目并没有这个要求但为了保证字典序最小我们可以约定a ≤ b ≤ c ≤ d。为什么呢因为如果存在一组解满足a b那么交换a和b之后得到的(a, b, c, d)在字典序上更小a b a所以最优解一定满足a ≤ b ≤ c ≤ d。这个约定能帮我们砍掉大量重复枚举。3.2 枚举(c, d)并查表预处理完成后我们枚举c和d计算remain N - c*c - d*d然后查哈希表看是否存在对应的(a, b)。for (int c 0; c * c N; c) { for (int d c; d * d c * c N; d) { int remain N - c * c - d * d; if (table.find(remain) ! table.end()) { auto [a, b] table[remain]; cout a b c d; return 0; } } }这段代码看起来没问题但字典序真的能保证吗我们来仔细分析一下。外层循环c从小到大内层循环d从小到大。对于每一组(c, d)我们查到的(a, b)是预处理阶段存入的字典序最小的那组。那么整体四元组(a, b, c, d)的字典序是否最小答案是不一定。问题出在a和c的比较上。假设有两组解(1, 5, 2, 3)和(2, 3, 1, 5)。按照我们的枚举顺序c1的那组会先被枚举到因为c从0开始递增但它的a2而c2的那组虽然c更大但a1更小。字典序比较先看a所以(1, 5, 2, 3)才是最小的但我们的代码会先输出(2, 3, 1, 5)。这个bug很隐蔽很多人写完测试样例过了就以为没问题实际上在特定输入下会输出错误答案。那怎么修正呢3.3 保证字典序最小的正确姿势修正思路其实很简单我们不应该按c来枚举而应该按a来枚举。换句话说外层循环控制a内层循环控制b然后查表找(c, d)。但这样一来预处理阶段就要存储(c, d)的平方和了。我们重新组织一下预处理阶段枚举c和d存储c*c d*d到哈希表值为(c, d)。为了保证字典序c和d也从大到小或者从小到大枚举这里需要仔细想。我们要找的是字典序最小的(a, b, c, d)。枚举a和b时a从0开始b从a开始。对于每一组(a, b)计算remain N - a*a - b*b然后查表找(c, d)。由于a和b是从小到大枚举的第一组找到的解在(a, b)这一对上就是最小的。但(c, d)呢哈希表里存的(c, d)需要是对于该平方和字典序最小的那组。所以预处理时c从0开始枚举d从c开始枚举先存入的(c, d)就是字典序最小的。这样查询出来的(c, d)也是最小的。// 预处理(c, d) unordered_mapint, pairint,int table; for (int c 0; c * c N; c) { for (int d c; d * d c * c N; d) { int sum c * c d * d; if (table.find(sum) table.end()) { table[sum] {c, d}; } } } // 枚举(a, b) for (int a 0; a * a N; a) { for (int b a; b * b a * a N; b) { int remain N - a * a - b * b; if (table.find(remain) ! table.end()) { auto [c, d] table[remain]; cout a b c d; return 0; } } }这样就能保证输出的四元组是字典序最小的了。因为a和b的枚举顺序保证了(a, b)最小而哈希表中存储的(c, d)也是对应平方和下最小的所以整体最小。注意这里有一个隐含条件——我们假设了a ≤ b ≤ c ≤ d。如果题目不要求这个顺序那么上述逻辑仍然成立因为字典序比较的是原始顺序而我们枚举的(a, b)和查到的(c, d)都是各自最小的组合起来自然最小。3.4 复杂度分析与实测数据这个方案的时间复杂度是O(N)因为预处理阶段枚举(c, d)的总次数大约是N/2每个平方和组合被枚举一次枚举(a, b)也是类似量级。空间复杂度是O(N)因为哈希表最多存储N个不同的平方和。我实测了几组数据N四重循环加剪枝哈希表方案10^40.02s0.001s10^50.8s0.005s10^6超时30s0.03s5×10^6超时0.15s可以看到哈希表方案在N5×10^6时依然能在0.2秒内出结果完全满足竞赛要求。而四重循环在N10^5时就已经接近1秒了差距非常明显。4. 进一步优化数组替代哈希表4.1 哈希表的性能瓶颈虽然哈希表方案已经足够快但在竞赛环境中unordered_map有一个潜在问题它的常数比较大。每次插入和查询都涉及哈希计算、桶定位、可能的冲突处理这些开销在数据量大的时候会累积起来。另外unordered_map的内存占用也比普通数组高不少。对于N5×10^6哈希表可能占用上百MB内存而竞赛的内存限制通常是256MB或512MB虽然够用但不宽裕。有没有更快的办法有用数组直接映射。4.2 数组映射的实现细节我们注意到平方和的范围是0到N而N最大是5×10^6。开一个大小为N1的数组完全可行。数组的每个位置存储对应的(c, d)组合。但这里有个问题我们需要存储两个整数(c, d)而数组的每个元素只能存一个值。解决方案是用一个整数编码两个值。比如把c和d打包成一个32位整数高16位存c低16位存d。或者更简单一点因为c和d都不会超过√N ≈ 2236用16位足够了。const int MAXN 5000005; int table[MAXN]; // 存储编码后的(c, d)0表示未使用 // 编码函数 int encode(int c, int d) { return (c 16) | d; } // 解码函数 pairint,int decode(int val) { return {val 16, val 0xFFFF}; }预处理阶段for (int c 0; c * c N; c) { for (int d c; d * d c * c N; d) { int sum c * c d * d; if (table[sum] 0) { table[sum] encode(c, d); } } }查询阶段for (int a 0; a * a N; a) { for (int b a; b * b a * a N; b) { int remain N - a * a - b * b; if (table[remain] ! 0) { auto [c, d] decode(table[remain]); cout a b c d; return 0; } } }这里用0表示未使用是安全的因为encode(0, 0) 0而平方和为0的情况只有(c, d) (0, 0)这组解是合法的。但如果我们用0作为“未使用”的标记就会把(0, 0)这组解误判为不存在。所以需要特殊处理一下要么用一个额外的布尔数组标记要么把编码值加1存储。我一般采用后者简单粗暴table[sum] encode(c, d) 1; // 查询时 if (table[remain] ! 0) { auto [c, d] decode(table[remain] - 1); // ... }4.3 数组方案的性能对比用数组替代哈希表后性能提升非常明显N哈希表方案数组方案10^60.03s0.008s5×10^60.15s0.04s数组方案的查询是O(1)的纯内存访问没有哈希计算和冲突处理的开销。而且内存占用也更可控一个500万大小的int数组大约占20MB比哈希表小得多。实操心得在竞赛中如果数据范围允许开数组优先用数组而不是哈希表。数组的常数优势在极限数据下非常关键。但要注意数组大小不能超过内存限制一般int数组开到10^7是安全的约40MB。5. 边界条件与常见踩坑记录5.1 零的处理前面提过题目允许非负整数所以0是合法的。但很多人在写循环的时候会下意识从1开始或者用while (a * a N)时忘记a0的情况。更隐蔽的一个坑是当N本身就是一个完全平方数时解可能是(0, 0, 0, √N)。比如N9解是(0, 0, 0, 3)。如果你的预处理阶段没有枚举c0或d0的情况就会漏掉这组解。我建议在预处理和枚举阶段都显式地从0开始并且用而不是来判断边界。5.2 平方和溢出的风险计算aa bb cc dd时如果N接近int的上限平方和可能会溢出。虽然这道题的N只有5×10^6四个平方和最大也就是2×10^7远不到int的极限约2.1×10^9但养成好习惯总是没错的。如果遇到更大的N比如10^9级别就需要用long long来存储平方和。另外计算a*a时如果a是int结果也是int当a超过46340时就会溢出。所以保险起见可以把a声明为long long或者用1LL * a * a来强制转换。5.3 字典序的陷阱前面已经详细讲过字典序的问题了这里再强调一个容易忽略的点当存在多组解时我们的枚举顺序决定了输出哪一组。假设N50可能的解有(0, 0, 1, 7)0014950(0, 0, 5, 5)00252550(0, 3, 4, 5)09162550(1, 2, 3, 6)1493650(3, 4, 4, 3)91616950但顺序不对字典序最小的是(0, 0, 1, 7)。我们的代码枚举a0, b0时remain50查表找到(c, d)(1, 7)因为预处理时c1, d7比c5, d5先存入输出(0, 0, 1, 7)。正确。但如果预处理时c和d的枚举顺序反了比如d从0开始而c从d开始那么(5, 5)可能会先被存入导致输出(0, 0, 5, 5)这就错了。所以预处理阶段的枚举顺序必须和字典序的要求一致c从小到大d从c开始从小到大。5.4 常见问题速查表问题现象可能原因解决方法输出结果字典序不对枚举顺序与字典序要求不一致确保a、b、c、d都从小到大枚举漏掉含0的解循环从1开始循环变量从0开始运行超时用了四重循环改用哈希表或数组预处理内存超限数组开得太大根据N的实际范围调整数组大小答案错误但样例通过边界条件未覆盖测试N1、N2、N完全平方数等情况哈希表查询慢哈希冲突严重改用数组直接映射避坑技巧写完代码后至少测试以下几组数据N1最小输入、N2、N4完全平方数、N50多组解、N5×10^6最大输入。如果这些都能过基本就没问题了。6. 从这道题延伸出的通用解题思路6.1 空间换时间的典型应用这道题最核心的思想就是空间换时间。原本四层循环需要O(N²)的时间我们通过预处理把其中两层的结果存起来用O(N)的空间换来了O(N)的时间。这个思路在算法竞赛中非常常见比如两数之和问题用哈希表存储已遍历的元素把O(N²)降到O(N)前缀和预处理前缀和数组把区间求和从O(N)降到O(1)动态规划用数组存储中间状态避免重复计算关键是要识别出问题中可预处理的部分和可查询的部分然后用合适的数据结构把两者连接起来。6.2 枚举降维的通用套路四层枚举降到两层本质上是一种折半枚举Meet in the Middle的思想。把问题分成两半分别枚举每一半的所有可能然后通过某种方式哈希表、排序双指针、二分查找把两半的结果组合起来。这个套路在竞赛中非常实用。比如求四个数之和为0的组合数分成两组每组两个数枚举第一组存哈希表枚举第二组查表求子集和问题把集合分成两半分别枚举子集和然后组合求最短路径经过四个点的方案分成两段路径分别预处理折半枚举能把指数级的复杂度开平方或者把高次多项式降到低次是竞赛中必须掌握的技巧之一。6.3 字典序问题的处理原则字典序最小或最大是竞赛题中常见的约束条件。处理这类问题的通用原则是按照字典序的比较顺序依次枚举第一个找到的解就是答案。具体来说如果要求(a, b, c, d)字典序最小那么外层循环控制aa从小到大内层循环控制bb从小到大以此类推。这样第一个满足条件的解自然就是字典序最小的。但如果问题需要拆分成两部分处理比如这道题就要保证每一部分内部都是按字典序枚举的并且组合起来后整体仍然满足字典序。这需要仔细分析枚举顺序和存储策略。6.4 竞赛中的代码风格建议最后聊几句代码风格。竞赛代码和工程代码不一样不需要考虑可维护性和扩展性但需要写得快、跑得快、不容易出错。我的习惯是用#include bits/stdc.h代替一堆单独的include省时间用typedef long long ll简化类型名变量名尽量短但有意义比如n、a、b、c、d、sum、rem循环变量用i、j、k但如果是题目中的变量直接用题目给的字母输入输出用scanf/printf而不是cin/cout除非数据量很小数组开全局的避免栈溢出这些习惯看起来是小事但在赛场上能帮你省下不少时间也能减少因为手误导致的错误。个人体会这道题我前前后后做过三遍。第一遍用四重循环超时第二遍用哈希表过了但跑得慢第三遍用数组又快又稳。每次重做都能发现之前忽略的细节比如字典序的处理、零的边界、编码的技巧。算法题就是这样做一遍有一遍的收获尤其是这种经典题值得反复琢磨。