以练代学：用竞赛真题学算法——暴力

先上题目出自蓝桥杯省赛真题题目描述四平方和定理又称为拉格朗日定理每个正整数都可以表示为至多 4 个正整数的平方和。如果把 0 包括进去就正好可以表示为 4 个数的平方和。比如5 0² 0² 1² 2²7 1² 1² 1² 2²对于一个给定的正整数可能存在多种平方和的表示法。要求你对 4 个数排序0 ≤ a ≤ b ≤ c ≤ d并对所有的可能表示法按 a, b, c, d 为联合主键升序排列最后输出第一个表示法。输入描述程序输入为一个正整数 N。数据范围N 5 × 10⁶输出描述输出 4 个非负整数按从小到大排序中间用空格分开。问题分析拿到这道题很多同学会纠结数据范围到 500 万是不是要用哈希、二分、动态规划但在蓝桥杯考试中最稳妥、最容易写、最不容易出错、最节省思考时间的方法其实是优化版暴力枚举。暴力法不是无脑循环而是带着约束条件去枚举把四层循环降到三层循环甚至两层循环在题目时间限制内跑出答案。为什么暴力能过我们利用约束条件 0 ≤ a ≤ b ≤ c ≤ d 来剪枝a 不需要循环太大a 最大只能到sqrt(N/4)b 不需要循环太大b 最大只能到sqrt((N-a²)/3)c 不需要循环太大c 最大只能到sqrt((N-a²-b²)/2)d 不需要循环直接算d² N - a² - b² - c²再判断是不是完全平方数这样一来原本恐怖的四层循环瞬间变成效率极高的三层循环500 万的数据完全可以轻松跑过。暴力解题思路枚举 a从 0 开始保证字典序最小枚举 b从 a 开始枚举 c从 b 开始计算剩余的值rest N - a² - b² - c²计算d sqrt(rest)判断d*d rest第一个满足条件的 a,b,c,d 就是答案直接输出因为我们从小到大枚举找到的第一个解一定就是题目要求的字典序最小解。代码演示c#include iostream #include cmath using namespace std; int main() { int N; cin N; // 枚举 aa 最小保证字典序 for (int a 0; a * a * 4 N; a) { // 枚举 b从 a 开始 for (int b a; b * b * 3 a * a N; b) { // 枚举 c从 b 开始 for (int c b; c * c * 2 b * b a * a N; c) { // 计算剩余的平方 int rest N - a * a - b * b - c * c; int d sqrt(rest); // 判断是否是完全平方数且 d c if (d * d rest d c) { cout a b c d endl; return 0; // 找到第一个直接退出 } } } } return 0; }pythonimport math n int(input()) # 暴力枚举 a 0 while a * a * 4 n: b a while b * b * 3 a * a n: c b while c * c * 2 b * b a * a n: rest n - a**2 - b**2 - c**2 d int(math.sqrt(rest)) if d * d rest and d c: print(a, b, c, d) exit() c 1 b 1 a 1算法详解这道题是蓝桥杯暴力枚举思想的最典型代表。很多同学看不起暴力觉得暴力太低级但在比赛中暴力往往是救命稻草。1. 暴力的核心剪枝约束条件暴力不是乱搜而是带着规则去搜。本题的剪枝条件就是a ≤ b ≤ c ≤ d每一层循环都严格限制上界绝不做无用功比如a 最大不超过sqrt(N/4)因为后面还有 3 个比它大的数b 最大不超过sqrt((N-a²)/3)c 最大不超过sqrt((N-a²-b²)/2)这些剪枝让循环次数直接减少几百几千倍速度飞快。2. 为什么不枚举 d因为 d 可以直接算出来d² N - a² - b² - c²我们只需要判断右边是不是完全平方数即可。少一层循环速度提升一个量级。3. 为什么找到第一个就输出因为我们是从小到大按顺序枚举a 从 0 开始b 从 a 开始c 从 b 开始所以第一个找到的合法解一定是字典序最小的解完全符合题目要求。4. 时间复杂度看似三层循环实际因为剪枝极强运行次数非常少。对于 N5e6运行次数通常在几万几十万次C 毫秒出解Python 也能轻松通过。结语这道四平方和是蓝桥杯最经典的暴力枚举入门题也是最能体现 “优化暴力” 思想的题目。