1. 从“题解”到“解题思维”一份迟到的复盘看到“2017年第八届国赛A~E题CB组题解”这个标题很多参加过蓝桥杯、ACM等算法竞赛的朋友可能会会心一笑。这像是一份尘封的“参考答案”或者一份赛后复盘笔记。但今天我并不打算仅仅罗列五道题的代码和答案——那在网上或许能找到更标准的版本。我更想做的是借由这五道具体的题目和你一起复盘一种更重要的东西面对算法竞赛题目的系统性解题思维与工程化编码习惯。2017年的题目其考察的知识点在今天看来依然经典模拟、搜索、动态规划、数论、贪心。这些是算法竞赛的基石也是很多实际开发场景如路径规划、资源调度、规则引擎的底层逻辑。对于正在备赛的同学这份复盘能帮你跳出“背模板”的误区理解每类题目背后的“为什么这么解”对于已经工作的开发者重温这些纯粹的算法问题能有效锻炼逻辑的严谨性对抗日常业务开发中可能形成的思维定式。所以这篇文章的核心不是答案本身而是拆解每道题从理解题意、抽象模型、选择算法、到编码实现与边界处理的完整思考链路。我会假设你具备C基础语法和基本的数据结构知识我们将一起像侦探一样剖析题目给出的线索并最终用代码优雅地呈现解决方案。你会发现解题的乐趣远大于得到一个“Accepted”。2. 第一战A题购物单——模拟与精度处理的开门红通常竞赛的A题会设计得相对直接用于稳定心态和热身。2017年的A题“购物单”正是这样一道题它考察的核心是模拟能力和浮点数计算的精度意识。题目大意是给出一个购物清单包括物品的单价、数量、折扣类型如“半价”、“八折”要求计算总金额。2.1 问题抽象与输入处理陷阱这道题看起来就是一个简单的算术题。但竞赛题的第一个坑往往藏在输入输出格式里。题目给出的数据可能是以空格或换行分隔的。我们需要稳健地读入所有数据。一个常见的“学生思维”是手动计算但作为程序我们必须处理任意多条商品记录。更关键的是数据类型的选取。单价和折扣涉及小数运算。在C中你是选择float、double还是int以分为单位存储这里就体现了经验在涉及金额、且可能需要进行多步乘除运算时应优先考虑使用double来保证精度或者在最初就将所有金额转换为整数分int或long long来避免浮点误差。对于本题因为折扣可能是“八折”0.8、“半价”0.5使用double是直观的但最后输出时需要注意格式化例如保留两位小数。注意在实际比赛中如果题目明确要求输出金额且没有特别说明使用double并配合printf(“%.2f”, total)输出是常规做法。但要警惕极端情况下的精度累积误差虽然本题数据量不大不会触发但这种意识很重要。2.2 核心逻辑实现与代码结构模拟题的代码结构通常很清晰。我们可以设计一个循环持续读入数据直到文件结束EOF。对于每一条记录读入单价、数量、折扣率。折扣率需要从字符串如“半价”映射为数值0.5。这里可以用if-else或mapstring, double来处理。一个良好的习惯是即使题目简单也将不同的功能模块化。例如可以写一个函数double parseDiscount(const string disc)来专门处理折扣字符串的解析。这会让代码更清晰在调试时也更容易定位问题。核心计算片段示意double total 0.0; double price; int quantity; string discount; while (cin price quantity discount) { double discRate parseDiscount(discount); total price * quantity * discRate; } printf(“%.2f\n”, total);2.3 为什么从A题开始强调这些因为A题定下了整场比赛的基调仔细审题、稳健处理输入输出、注意数据类型。很多选手在更复杂的题目上绞尽脑汁却可能在A题因为浮点输出格式错误比如多了个空格而丢分这是非常可惜的。把简单的题做对、做稳是积累信心的关键。3. 第二关B题等差素数列——数论与暴力枚举的艺术B题“等差素数列”将难度提升了一个档次它融合了数论素数判断和枚举思想。题目要求我们找到一个长度为10的等差素数列并输出其公差。这意味着我们需要在素数集合中寻找一个等差数列。3.1 暴力搜索的边界与优化最朴素的想法是枚举所有素数作为数列首项枚举所有可能的公差检查以该首项和公差生成的10个数是否都是素数。但素数有无穷多个公差也可以很大完全的暴力枚举不可行。这里就需要我们寻找搜索空间的上下界。题目隐含了条件通常来自题设或样例这个数列的数值不会超过一个范围比如100万以内。我们需要预先筛选出这个范围内的所有素数。这引出了算法竞赛中一个经典的基础组件素数筛法尤其是埃拉托斯特尼筛法埃氏筛或欧拉筛线性筛。对于百万级别的数据埃氏筛时间复杂度O(n log log n)完全够用且编码简单。const int MAX_N 1000000; bool isPrime[MAX_N 1]; vectorint primes; void sieve() { fill(isPrime, isPrime MAX_N 1, true); isPrime[0] isPrime[1] false; for (int i 2; i MAX_N; i) { if (isPrime[i]) { primes.push_back(i); for (int j i * 2; j MAX_N; j i) { isPrime[j] false; } } } }3.2 构造与验证的逻辑有了素数表isPrime我们的枚举就变得可行了。外层循环遍历所有可能的素数作为首项a。内层循环枚举公差d。这里d的枚举范围也需要考量因为数列增长a 9*d不能超过我们筛法的上限。同时d可以从1开始但显然如果a和d不互素那么数列中必然会出现合数所以更优的做法是只枚举d为正整数而依赖后续的快速检查。对于每一组(a, d)我们写一个循环检查a, ad, a2d, ..., a9*d这10个数是否都在素数表中。一旦全部通过我们就找到了答案。3.3 从这道题中学到的策略这道题教会我们两点1.“空间换时间”的预处理思想。提前打好素数表使得后续每次素数判断都是O(1)操作极大降低了整体复杂度。2.对暴力枚举进行有效剪枝。通过分析问题约束数列长度、数值范围我们合理限制了首项和公差的枚举范围让暴力搜索变得可行。在竞赛中很多题目看似需要高深算法实则通过巧妙的枚举和预处理就能解决。4. 核心战场C题承压计算——二维递推与数值精度陷阱C题“承压计算”是一个经典的二维模拟递推问题带有物理背景压力传导。题目描述了一个金字塔形的容器最上层若干位置有已知重量的物品重量会均匀分给下方支撑它的两个支点。要求计算最下层各个位置的“承压”并找出最小值和最大值进行某种比例换算。4.1 建立数学模型与递推关系这是典型的二维动态规划/递推问题。我们可以用一个二维数组weight[i][j]来表示第i行第j个位置承受的总重量包含自身可能有的物品。金字塔的层数已知例如30层。递推关系非常清晰对于第i行第j个位置假设下标从1开始它承受的重量来源于上方第i-1行的第j-1和第j个位置如果存在。并且上方每个位置会将其重量的一半传递下来。因此递推公式为weight[i][j] (weight[i-1][j-1] / 2) (weight[i-1][j] / 2) own_weight[i][j]其中own_weight[i][j]是题目直接放在该位置的物品重量对于大多数位置为0。初始化时将题目给出的顶层物品重量填入weight[1][?]即可。然后从第2层开始逐层向下计算。4.2 精度问题的终极挑战与解决方案本题最大的坑也是区分度所在就是精度。即便使用double在经历数十层的除以2操作后累积的浮点误差也可能导致最终结果特别是最值之间的比例与标准答案有微小出入。在竞赛的判题系统中这可能导致“Wrong Answer”。如何解决一个经典且有效的技巧是使用整数运算通过放大倍数来模拟小数。既然每次都是除以2我们可以让初始重量不是实际重量而是实际重量乘以一个很大的2的幂比如2^30。这样每次“除以2”的操作就变成了对这个整数的右移运算或者直接除以2因为整除在整个计算过程中完全不涉及浮点数。最后当我们得到最底层的整数“承压值”后再将其除以放大倍数得到实际值进行比较。例如long long weight[35][35]; // 使用 long long 防止溢出 const long long factor 1LL 30; // 放大倍数 2^30 // 初始化顶层放入物品的重量为 w则 weight[1][pos] w * factor; // 递推过程weight[i][j] (weight[i-1][j-1] / 2) (weight[i-1][j] / 2); // 注意因为 weight 已经是放大后的值这里的除以2是整数除法模拟了实际重量的半分。4.3 思维跃迁从模拟到优化这道题体现了将实际问题转化为可计算模型的能力。更重要的是它警示我们当算法思路正确却仍然无法AC时问题可能出在数据表示上。精度问题是算法竞赛中一个隐蔽的敌人对于涉及大量乘除、特别是除法运算的题目整数化往往是利器。这种“放大整数”的思路在金融、游戏等对精度要求高的领域也有实际应用。5. 攻坚克难D题方格分割——深度优先搜索(DFS)与对称性剪枝D题“方格分割”是一道非常精彩的搜索题。题目在一个6x6的方格矩阵注意是格点共7x7个点上要求沿着格线切割将方格图分割成完全对称的两部分。求有多少种不同的分割方案。切割线必须从边界的中点开始结束于另一个边界的中点。5.1 问题转化与搜索状态设计初看此题可能无从下手。关键在于转化视角切割线关于中心点(3,3)中心对称。因此我们只需要搜索从中心点出发到达边界的一条路径同时这条路径的对称路径会自动生成。由于两部分完全对称一旦我们搜索出一条从中心到边界的路径其对称部分就构成了另一条从中心到对称边界点的路径从而完成了整个切割。因此问题转化为从网格中心点(3,3)出发每次向上、下、左、右四个方向移动一格搜索所有能够到达边界的路径并且路径不能重复经过同一个点。同时因为对称性我们搜索的路径和其对称路径不能有交集否则相当于切割线自交这要求在搜索过程中当走到一个点(x,y)时需要同时标记其对称点(6-x, 6-y)为已访问。5.2 DFS实现与细节处理我们可以使用深度优先搜索DFS来遍历所有可能的路径。状态当前坐标(x, y)。目标x 0 || x 6 || y 0 || y 6到达边界。约束不能走出网格范围0-6不能访问已标记的点包括对称点。动作向四个方向移动。剪枝利用对称性由于旋转对称最终方案数会有重复。一种常见的处理方法是因为从中心出发第一步有四个方向但最终分割方案是旋转对称的我们可以固定第一步的方向比如向下或向右这样搜索出来的结果乘以4就是最终答案。这能有效减少搜索量。DFS函数框架int visited[7][7] {0}; int directions[4][2] {{1,0}, {-1,0}, {0,1}, {0,-1}}; int ans 0; void dfs(int x, int y) { if (x 0 || x 6 || y 0 || y 6) { ans; return; } for (int i 0; i 4; i) { int nx x directions[i][0]; int ny y directions[i][1]; int sym_x 6 - nx; int sym_y 6 - ny; if (nx 0 nx 6 ny 0 ny 6 !visited[nx][ny] !visited[sym_x][sym_y]) { visited[nx][ny] visited[sym_x][sym_y] 1; // 标记当前点及其对称点 dfs(nx, ny); visited[nx][ny] visited[sym_x][sym_y] 0; // 回溯 } } } // 初始化从中心(3,3)开始需要先标记(3,3)及其对称点(3,3)其实是同一点 visited[3][3] 1; dfs(3, 3); // 最终答案 ans 需要根据剪枝策略处理例如如果固定了第一步则 ans * 45.3 搜索题的核心状态空间与剪枝这道题是搜索算法的典型应用。它告诉我们面对看似复杂的组合问题寻找问题的对称性、等价性从而缩小搜索空间是至关重要的第一步。设计清晰、无冗余的搜索状态并施加有效的剪枝条件如对称标记、固定起点方向才能让DFS在有限的时间内跑出结果。否则搜索空间会指数级膨胀导致程序超时TLE。6. 最终挑战E题取位数——递归与代码填空的思维体操E题“取位数”通常是一道代码填空题考察对递归或迭代算法的理解。题目可能给出一个函数框架要求填写关键代码实现从整数中取出特定位数的数字。例如f(x)表示取x的个位数f(f(x))表示取十位数以此类推。6.1 理解递归的“递”与“归”这类题目的核心是理解函数嵌套调用的过程。假设函数int f(int x)的功能是返回x的个位数那么f(f(x))的执行过程是计算内层f(x)得到x的个位数假设为a。计算外层f(a)即取a的个位数。由于a本身是个位数所以f(a) a。 这显然不符合取十位数的本意。因此正确的f(x)应该实现的是“去掉个位数”的功能而不是“取出个位数”。这样f(x)返回x/10去掉个位后的数。f(f(x))先执行内层f(x)x/10得到去掉个位后的数再执行外层f(x/10) (x/10)/10 x/100相当于去掉了最后两位。 那么如果我们想取第k位数字从个位为1开始可以通过g(x) x % 10取个位而f函数负责“移位”。所以要取十位数应该是g(f(x))取百位数是g(f(f(x)))。题目可能给出的填空就是让你实现这个“移位”函数f。6.2 常见变体与应对策略代码填空的变体很多可能考察递归求余、递归进制转换、或者利用静态变量进行迭代计数等。关键是要手动模拟几次小规模的调用理解输入和输出的对应关系。例如可以假设x 12345然后手动计算f(12345)、f(f(12345))应该是什么再去看代码框架中缺少的部分应该完成什么运算。一个典型的填空题可能长这样// 求x的10进制表示中的第k位数字个位是第1位 int digit(int x, int k) { if (k 1) { return x % 10; } return ____________________; // 填空 }答案应该是digit(x / 10, k - 1)。这体现了递归思想取第k位等价于先去掉个位x/10然后在剩下的数中取第k-1位。6.3 填空题的得分哲学代码填空题是“送分题”但也是“送命题”因为它要求完全精确的理解。策略是务必结合样例进行纸笔模拟。将中间变量写出来跟踪每一步执行过程。填空后用题目给的样例数据验证一下。这类题考察的是扎实的基本功和清晰的逻辑没有取巧的余地但一旦掌握规律就能快速拿分。7. 跨越七年的启示竞赛思维对工程实践的滋养回顾这五道题从简单的模拟到复杂的搜索它们像一套完整的思维体操。2017年的赛题在今天依然有价值因为它训练的是程序员的核心内功严谨性A题和C题警示我们忽略输入输出格式、轻视数值精度会在最简单的地方跌倒。预处理与空间换时间B题的素数筛告诉我们良好的准备工作能极大提升后续效率。这在工程中对应着缓存、索引等优化手段。建模能力C题和D题都需要将文字描述转化为精确的数据模型和算法步骤。这是解决任何复杂业务需求的必备能力。搜索与优化D题是搜索算法的经典应用其剪枝思想在解决资源分配、路径规划等NP-Hard问题的启发式算法中随处可见。基础算法深度理解E题考察的递归是理解树、图、分治等高级算法的基础。刷题的目的从来不只是为了比赛。通过这样的系统性复盘我们锻炼的是一种“拆解-抽象-实现-优化”的肌肉记忆。当你在工作中遇到一个模糊的需求时能下意识地开始边界梳理、数据建模和方案选型这就是算法训练带来的最大红利。最后分享一个我个人的习惯每做完一道题尤其是做错的题不要仅仅满足于AC而是问自己三个问题“这道题的核心考点是什么”、“我的第一个错误思路是什么为什么错”、“有没有更优、更通用的解法”。坚持这样复盘成长的速度会远超你的想象。