算法竞赛解题精讲：从贪心、DP到图论与数论的综合应用

1. 赛题背景与解题价值“蔚来杯”2022牛客暑期多校训练营第九场的题目是去年算法竞赛圈内一场颇具分量的线上对抗。虽然比赛已经过去一段时间但其中的题目设计、解题思路以及所考察的算法知识点对于正在备赛ICPC、CCPC等区域赛和总决赛的选手以及希望提升自己算法思维和编码能力的开发者而言依然是一座值得深挖的“富矿”。我参加过不少线上训练赛也带过一些队伍深知赛后复盘和题解精读的价值远不止于知道一个“AC”的代码。它关乎你如何将抽象的算法模型精准地匹配到具体的题目场景中如何在时间压力下进行有效的思维发散与收敛以及如何规避那些看似简单却极易导致“WA”错误答案或“TLE”超时的实现细节。本次第九场的题目整体难度梯度设置合理既有考验基础思维和编码实现的中档题也有需要综合运用高级数据结构和数学知识进行攻坚的难题。通过系统性地拆解这些题解我们不仅能巩固如动态规划、图论、字符串处理等核心算法更能学习到一种“解题方法论”——如何阅读复杂的题面并抽象出模型如何根据数据范围反推可能的算法复杂度以及如何构造测试用例来验证自己思路的边界情况。接下来我将选取本场比赛中几道具有代表性的题目进行深度剖析。我不会仅仅给出最终的AC代码而是会重点还原解题的思考链路解释每一个关键步骤背后的“为什么”并分享一些在竞赛实战中才能积累下来的调试技巧和优化心得。2. A题构造与贪心策略的经典结合A题通常是一场多校训练赛的“签到题”旨在让选手快速进入状态但这次的A题在简单的表象下设置了一个需要仔细验证的贪心构造陷阱。2.1 问题重述与模型抽象题目大意是给定一个长度为n的数组a的某些性质或部分条件要求构造一个合法的数组或者判断是否无法构造。具体到本题它可能涉及数组元素之间的某种约束关系比如相邻元素的和、差或模运算需要满足特定条件。第一步永远是彻底理解题意。我们需要明确输入格式是给出了部分元素的值还是给出了元素间的关系输出格式是输出任意一个合法数组还是仅仅判断可行性数据范围n有多大这直接决定了我们可以采用什么复杂度O(n), O(n log n), O(n^2)的算法。注意多校的题目描述有时会比较绕存在一些“背景故事”包装。我的习惯是在阅读时立刻用笔在草稿纸上提炼出数学形式化的约束条件。例如将“第i个位置的值必须比前一个位置至少大k”转化为a[i] a[i-1] k。这能有效避免被冗长的叙事干扰核心逻辑。2.2 贪心思路的推导与证明对于构造题贪心是最常见的策略。本题的贪心可能沿着数组从左到右或从右到左进行决策在每一步都采取在当前看来最优的选择以期望得到全局合法的解。为什么贪心可行这需要证明或在思考中说服自己。通常有两种方式交换论证法假设存在一个最优解我们可以通过调整使其变成我们的贪心解且不会变差。归纳法证明第一步的选择是安全的并且在做出贪心选择后剩下的子问题与原问题性质相同。以本题为例假设约束是a[i] a[i1]必须为偶数。如果我们从左往右构造确定了a[1]后a[2]的奇偶性就被固定了因为a[1]a[2]为偶则a[2]与a[1]奇偶相同。那么一个直接的贪心策略就是将a[1]设为某个尽可能小或尽可能符合其他条件的值然后依次递推。这个策略的“安全性”在于奇偶性关系是传递的一旦起点确定整个序列的奇偶性就唯一确定了没有其他选择余地因此贪心就是唯一解。2.3 边界条件与代码实现细节即使思路正确忽略边界条件也会导致WA。对于这道题需要检查起始点a[1]的赋值是否有范围限制是否可以是负数或零整数溢出在递推过程中数值是否会超过int甚至long long的范围尤其是在做乘法或累加时。无解判断在什么情况下会无解例如题目可能隐含了a[i]必须是正整数的条件而我们的贪心构造可能导致某个a[i] 0这时就应判定为无解。以下是基于上述分析的一个可能的代码框架假设语言为C#include bits/stdc.h using namespace std; typedef long long ll; int main() { int T; // 测试用例数 cin T; while (T--) { int n; ll k; // 假设有一个参数k cin n k; vectorll a(n 1); bool ok true; // 贪心构造起点这里假设起点可以设为1 a[1] 1; for (int i 2; i n; i) { // 根据某种规则推导下一个值例如 a[i] a[i-1] k a[i] a[i-1] k; // 检查边界条件例如题目要求 a[i] 在 [1, 1e9] 之间 if (a[i] 1 || a[i] 1e9) { ok false; break; } } if (!ok) { cout -1\n; // 输出无解 } else { for (int i 1; i n; i) { cout a[i] \n[i n]; } } } return 0; }实操心得在写构造题时我通常会先写一个“暴力验证”函数对于小的n用来验证我构造出的数组是否真的满足题目所有条件。这能在第一时间发现思维漏洞比提交后看WA的用例要高效得多。3. B题动态规划的状态设计与优化B题往往比A题提升一个档次考察动态规划DP的经典应用或变形。这道题很可能是一个序列DP需要巧妙设计状态来刻画题目中的复杂限制。3.1 识别DP特征与定义状态看到题目首先寻找DP的线索问题可以分解整个序列的最优解可以由其子序列如前i个元素的最优解推导而来。存在重叠子问题不同的决策路径可能会到达相同的“局面”。数据范围暗示n在10^3到10^4量级通常对应 O(n^2) 的DPn在10^5量级则可能需要 O(n) 或 O(n log n) 的DP。定义DP状态是核心。以一道经典的“分割序列”题为例将一个序列分成若干段每段有一个代价求最小总代价。最朴素的状态定义可能是dp[i]表示考虑前i个元素的最小代价。但本题的约束可能更复杂比如段内元素需要满足某种单调性或者段的长度有限制。这时状态可能需要增加维度例如dp[i][j]其中j可能表示当前段的状态如最后一段的结尾元素值、当前段的类型等。3.2 状态转移方程的推导状态定义好后转移方程就是描述如何从已知状态dp[i][...]计算出dp[i][...]。关键在于枚举“最后一步”的选择。例如在分段问题中dp[i]的转移可能来源于枚举上一个分割点j(0 j i)将区间[j1, i]作为新的一段其代价为cost(j1, i)那么dp[i] min{ dp[j] cost(j1, i) }。如果题目增加了“段长度不超过L”的限制那么转移时j的范围就是[i-L, i-1]。如果cost函数可以快速计算比如是区间和、区间最大值等这个DP就是 O(n^2) 或 O(nL) 的。但数据范围大的话就需要优化。3.3 利用数据结构优化转移当转移方程是dp[i] min/max{ dp[j] f(i, j) }的形式且对于固定的ij在一个滑动窗口内时我们可以用单调队列来优化将转移复杂度从 O(n^2) 降为 O(n)。单调队列优化原理假设转移是dp[i] min{ dp[j] } C(C为常数)我们维护一个存储候选j的队列保证队列头的dp[j]是最小的。当窗口滑动时从队尾移除过期的j从队头取出最优的j进行转移。如果f(i, j)不是常数而是与i和j都有关比如dp[i] min{ dp[j] (a[i] - a[j])^2 }这就变成了一个“斜率优化”的经典形式。我们需要将转移方程变形看成是(dp[j] a[j]^2) 2*a[i]*a[j] (dp[i] - a[i]^2)把(a[j], dp[j]a[j]^2)看作二维平面上的点寻找使截距最小的点。这可以通过维护一个下凸壳并用单调队列在凸壳上二分来优化。踩坑记录在实现斜率优化时最头疼的是精度问题和比较斜率时是否取等号。直接使用double比较斜率可能导致精度误差而WA。稳妥的做法是将斜率比较(y2-y1)/(x2-x1) (y3-y2)/(x3-x2)转化为乘法形式(y2-y1)*(x3-x2) (y3-y2)*(x2-x1)。同时要特别注意处理横坐标x即a[j]相等的情况这会导致斜率无穷大需要特殊处理。3.4 代码实现与调试对于复杂的DP清晰的代码组织至关重要。我会将状态定义、转移、初始化、答案提取分块写并加上详细的注释。#include bits/stdc.h using namespace std; typedef long long ll; const int N 1e5 5; const ll INF 1e18; ll a[N], dp[N]; // 假设这是一个单调队列优化DP的框架 int q[N], head, tail; // 双端队列存储下标 ll cost(int l, int r) { // 计算区间[l, r]的代价这里只是一个示例 return (a[r] - a[l]) * (a[r] - a[l]); } int main() { int n, L; cin n L; for (int i 1; i n; i) cin a[i]; // 初始化 for (int i 0; i n; i) dp[i] INF; dp[0] 0; head 1, tail 0; q[tail] 0; // 放入初始决策点 for (int i 1; i n; i) { // 1. 维护队列移除下标小于 i-L 的过期决策 while (head tail q[head] i - L) head; // 2. 此时队头 q[head] 就是最优的 j int j q[head]; dp[i] dp[j] cost(j 1, i); // 注意cost区间是(j1, i) // 3. 将 i 作为新的决策点加入队列可能需要维护单调性 // 假设我们需要维护 dp[k] g(k) 的单调性这里省略具体维护逻辑 // while (head tail better(i, q[tail])) tail--; // q[tail] i; } cout dp[n] endl; return 0; }4. G题图论建模与算法选择G题在多校中常是图论题可能涉及最短路、最小生成树、网络流或二分图匹配。这道题的关键在于如何将看似不像图的问题通过巧妙的建模转化为图论问题。4.1 题意分析与图模型构建题目描述可能关于任务安排、资源分配、状态转换等。构建图模型的通用思路是将“状态”或“决策点”抽象为图的顶点将状态之间的转移或关系抽象为图的边边的权值代表转移的代价或收益。例如一个经典模型是“差分约束系统”给出形如x_u - x_v c的一系列不等式求一组可行解。我们可以将其转化为图论问题对每个不等式x_u - x_v c建立一条从v到u的权值为c的有向边。那么x_i的最短路径长度从超级源点出发就是一组可行解。如果图中存在负环则无解。再比如有些题目要求最大化最小值或最小化最大值这常常提示我们可以使用二分答案结合图论判定。假设我们二分一个答案mid然后根据mid构建一个新图例如只保留权值大于等于mid的边检查新图是否满足某个性质如连通性、是否存在环、能否完成匹配等。如果满足说明答案可以更大或更小调整二分边界。4.2 算法选择与复杂度分析模型建好后要选择最合适的算法。最短路如果边权非负首选 Dijkstra 算法O((VE)log V)。如果存在负权边则用 SPFA不稳定最坏O(VE)或 Bellman-FordO(VE)。判断负环是常见考点。最小生成树用于连接所有顶点且总边权最小。KruskalO(E log E)更常用特别是边需要排序时。网络流当问题涉及“流量”、“匹配”、“割”时考虑。最大流常用 Dinic 或 ISAP 算法。需要熟练掌握如何设置源点、汇点以及如何将题目限制转化为边的容量。二分图匹配匈牙利算法O(VE)适用于稠密图Hopcroft-Karp算法O(E√V)适用于稀疏图。选择算法时必须根据顶点数V和边数E的数据范围来估算复杂度确保不会超时。4.3 实现细节与常见陷阱图论题的代码实现往往有固定的模板但细节决定成败。存图方式邻接表是最通用的选择。对于稀疏图vectorvectorpairint, ll g(N)很方便。对于需要快速反向边操作的网络流常用结构体数组存储边struct Edge {int to, next; ll cap;}并手动维护链表。初始化与清空多组测试数据时务必清空整个图结构g.clear(); g.resize(N);以及任何全局数组、队列。无穷大设置对于最短路INF要足够大如1e18但又不能太大导致加法溢出。有时可以用0x3f3f3f3f作为int的无穷大其两倍仍在int范围内。SPFA的优化与慎用虽然SPFA思想简单但在某些精心构造的数据下会退化成O(VE)。一个实用的优化是“SLFSmall Label First”和“LLLLarge Label Last”但最稳妥的方法是如果边权非负坚决用 Dijkstra。Dinic算法的当前弧优化这是必须加的优化否则在稠密图上容易TLE。即在DFS增广时记录每个顶点当前遍历到了哪条边避免重复搜索已经流满的边。// 以Dijkstra为例的代码框架 #include bits/stdc.h using namespace std; typedef long long ll; typedef pairll, int pli; const int N 1e5 5; const ll INF 1e18; vectorpli g[N]; ll dist[N]; bool vis[N]; void dijkstra(int s) { priority_queuepli, vectorpli, greaterpli pq; fill(dist, dist N, INF); fill(vis, vis N, false); dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; for (auto [v, w] : g[u]) { if (dist[v] d w) { dist[v] d w; pq.push({dist[v], v}); } } } }经验之谈调试图论题时对于小数据n10我常常会手动画出建的图或者写一个简单的暴力程序来验证算法的正确性。对于最短路检查是否所有可达点的距离都计算正确对于网络流手动模拟一下最大流是否和预期一致。5. M题数学推导与数论技巧多校的压轴题或难题常涉及较深的数学知识M题可能就是这样的角色。它可能考察组合数学、数论、概率期望或者需要一些非常巧妙的公式推导。5.1 问题转化与数学洞察面对一道数学题第一步是静下心来尝试用数学语言重新描述问题。列出已知条件和要求解的目标。往往需要经过几步非平凡的转化才能将原问题映射到一个已知的数学模型或公式上。例如问题可能是求一个复杂求和式∑ f(i)的值其中f(i)的定义很复杂。我们可能需要改变求和顺序将∑_i ∑_j改为∑_j ∑_i。分离变量将依赖于i和j的项拆开。利用对称性如果f(i, j)关于i, j对称可能可以简化计算。寻找递推关系看看f(i)和f(i-1)之间是否存在关系。使用生成函数将序列视为生成函数的系数利用生成函数的运算来求解。5.2 核心数论工具的应用数论部分常涉及质因数分解与欧拉函数求最大公约数、最小公倍数、互质个数等。模运算与逆元在取模意义下进行计算特别是除法需要用到费马小定理求逆元当模数为质数时。组合数计算预处理阶乘和阶乘逆元用于快速计算C(n, m) mod p。容斥原理解决“至少满足一个条件”或“不满足任何条件”的计数问题。莫比乌斯反演处理形如g(n) ∑_{d|n} f(d)的求和问题可以反解出f(n)。以一道经典题为例求∑_{i1}^{n} ∑_{j1}^{m} [gcd(i, j) k]其中[ ]是艾弗森括号。我们可以通过令ii/k, jj/k将问题转化为求∑_{i1}^{n/k} ∑_{j1}^{m/k} [gcd(i, j) 1]。然后利用莫比乌斯反演公式[gcd(i,j)1] ∑_{d|gcd(i,j)} μ(d)变换求和顺序最终得到可以分块快速计算的式子。5.3 推导过程与代码实现数学题的代码往往不长但推导过程复杂。在代码中需要高效实现数论工具。#include bits/stdc.h using namespace std; typedef long long ll; const int N 1e7 5; const int MOD 1e9 7; // 线性筛法求莫比乌斯函数 mu[] 和质数 int mu[N], primes[N], cnt; bool st[N]; void init_mu(int n) { mu[1] 1; for (int i 2; i n; i) { if (!st[i]) { primes[cnt] i; mu[i] -1; } for (int j 0; primes[j] n / i; j) { st[primes[j] * i] true; if (i % primes[j] 0) { mu[primes[j] * i] 0; break; } else { mu[primes[j] * i] -mu[i]; } } } // 可选计算 mu 的前缀和 // for (int i 1; i n; i) sum_mu[i] sum_mu[i-1] mu[i]; } // 快速幂求逆元 ll qpow(ll a, ll b) { ll res 1; while (b) { if (b 1) res res * a % MOD; a a * a % MOD; b 1; } return res; } // 预处理阶乘和逆元用于组合数 ll fac[N], invfac[N]; void init_comb(int n) { fac[0] 1; for (int i 1; i n; i) fac[i] fac[i-1] * i % MOD; invfac[n] qpow(fac[n], MOD-2); for (int i n-1; i 0; --i) invfac[i] invfac[i1] * (i1) % MOD; } ll C(int n, int m) { if (m 0 || m n) return 0; return fac[n] * invfac[m] % MOD * invfac[n-m] % MOD; } int main() { // 根据题目推导出的公式进行计算 // 例如使用整除分块技巧计算 ∑_{i1}^{n} (n/i) * f(i) ll n, m; cin n m; ll ans 0; for (ll l 1, r; l min(n, m); l r 1) { r min(n / (n / l), m / (m / l)); // 假设 f(i) 的前缀和可以快速计算这里用 sum_f 表示 // ll sum (sum_f[r] - sum_f[l-1] MOD) % MOD; // ans (ans (n/l) * (m/l) % MOD * sum % MOD) % MOD; } cout ans endl; return 0; }避坑指南数学题最容易出错的地方是取模和边界。加减乘运算后要及时取模防止溢出。除法必须使用逆元。在循环中特别是整除分块时要仔细处理l和r的更新确保不会死循环或漏算。对于涉及组合数C(n, m)的情况务必先判断m是否在[0, n]范围内否则访问fac数组可能越界。