1. 从赛题到题解一场团队赛背后的算法思维拆解如果你打过几场程序设计竞赛大概会有这样的体会赛后看题解往往比比赛时更让人拍大腿。比赛时卡了三个小时的题看完题解发现核心就是一个排序加贪心或者一个简单的动态规划转移。这种“原来如此”的瞬间正是竞赛最让人上瘾的地方。这次要聊的是某高校第二届程序设计大赛团队赛的完整题解拆解。团队赛和单人赛最大的区别在于分工与协作题目设计上通常会有意区分难度梯度让不同水平的队伍都能找到自己的节奏。这篇文章面向的是有一定编程基础、想通过真题来提升算法实战能力的同学也适合正在准备各类程序设计竞赛的选手作为训练参考。我会把每道题的核心考点、解题思路、代码实现以及比赛时容易踩的坑逐一拆开来讲清楚。团队赛的题目设置一般遵循“签到题—中档题—压轴题”的梯度。签到题考察基本语法和简单逻辑中档题涉及经典算法模型压轴题则需要组合多个知识点或者有巧妙的思维转换。这次比赛的题目整体难度分布比较合理没有出现那种“全场零通过”的极端情况但压轴题确实卡住了不少队伍。下面我按照题目类型分组来展开每道题都会给出完整的分析过程和可复现的代码。2. 签到题组别让简单题成为失分点2.1 第一题基础输入输出与边界处理签到题通常放在比赛的第一题目的是让所有队伍都能快速进入状态。这次的第一题是一个典型的数值统计问题给定一组整数要求统计其中满足特定条件的元素个数。题目描述很直白没有任何弯弯绕绕但恰恰是这种题最容易因为边界条件没考虑周全而丢分。核心逻辑就是遍历数组对每个元素做条件判断计数器加一。听起来简单到不需要思考但比赛时我见过太多队伍在这类题上翻车。常见的问题包括数据范围没看清导致用了错误的数据类型比如题目说数值可能达到10的9次方你用int存就可能溢出或者边界值处理不当比如条件里写的是“大于等于”你写成了“大于”。#include iostream #include vector using namespace std; int main() { int n; cin n; vectorlong long nums(n); for (int i 0; i n; i) { cin nums[i]; } long long threshold; cin threshold; int count 0; for (int i 0; i n; i) { if (nums[i] threshold) { count; } } cout count endl; return 0; }提示签到题最大的敌人是粗心。建议养成习惯读完题后先把数据范围、边界条件、输出格式这三项确认一遍再动手写代码。这道题还有一个容易被忽略的点输入格式。有些题目会明确说“第一行一个整数n第二行n个整数”但实际测试数据里可能存在多组输入的情况。虽然题目没明说但保险起见可以用while(cin n)的方式处理避免因为输入格式理解偏差导致全部WA。2.2 第二题字符串处理与模拟第二题是一道字符串模拟题要求对一个给定的字符串按照特定规则进行变换。这类题目的特点是逻辑不复杂但细节繁琐需要耐心地把每一步操作都实现正确。题目大意是给定一个只包含小写字母的字符串要求将其中连续重复的字符压缩比如“aaabbb”变成“a3b3”如果某个字符只出现一次则不写数字。这个规则本身不难但有几个细节需要注意一是压缩后的数字可能是多位数比如某个字符连续出现12次要输出“a12”而不是“a1a2”二是字符串末尾的连续字符也要正确处理不能漏掉。#include iostream #include string using namespace std; int main() { string s; cin s; string result; int n s.length(); for (int i 0; i n; ) { int j i; while (j n s[j] s[i]) { j; } int cnt j - i; result s[i]; if (cnt 1) { result to_string(cnt); } i j; } cout result endl; return 0; }注意字符串模拟题一定要在纸上或者注释里把样例手动走一遍确认每个分支都覆盖到了。特别是循环的起止条件差一个下标就可能导致结果完全错误。这道题还有一个变种考法就是解压缩也就是把“a3b3”还原成“aaabbb”。如果比赛时遇到的是解压缩版本思路类似但要注意数字可能是多位的情况需要先解析出完整的数字再重复字符。3. 中档题组经典算法的实战应用3.1 第三题贪心与排序的结合第三题是一道典型的贪心题题目背景是任务调度有n个任务每个任务有截止时间和耗时要求安排任务的执行顺序使得尽可能多的任务能在截止时间前完成。这道题的核心思路是按照截止时间从小到大排序然后依次处理每个任务用一个变量记录当前已消耗的时间如果加上当前任务耗时后不超过截止时间就执行该任务否则跳过当前任务继续看下一个。但这个贪心策略有一个问题如果跳过的任务耗时很长而后面有一个耗时短但截止时间稍晚的任务跳过前者执行后者可能更优。所以正确的做法是维护一个已选任务的最大堆按截止时间排序后依次遍历每次先把当前任务加入堆并累加耗时如果累加后的耗时超过了当前任务的截止时间就弹出堆中耗时最大的任务同时从总耗时中减去它。这样保证在任意时刻已选任务集合都是在满足截止时间约束下耗时最小的。#include iostream #include vector #include algorithm #include queue using namespace std; struct Task { int deadline; int duration; }; int main() { int n; cin n; vectorTask tasks(n); for (int i 0; i n; i) { cin tasks[i].deadline tasks[i].duration; } sort(tasks.begin(), tasks.end(), [](const Task a, const Task b) { return a.deadline b.deadline; }); priority_queueint pq; long long totalTime 0; for (int i 0; i n; i) { pq.push(tasks[i].duration); totalTime tasks[i].duration; if (totalTime tasks[i].deadline) { totalTime - pq.top(); pq.pop(); } } cout pq.size() endl; return 0; }提示贪心题的关键是证明贪心策略的正确性。比赛时如果时间紧张可以先写一个暴力解法对拍用小数据验证贪心策略是否成立再提交。这道题的时间复杂度是O(n log n)主要消耗在排序和堆操作上。数据范围如果达到10的5次方这个复杂度完全可以接受。但如果n更大比如10的6次方就需要考虑更高效的实现方式比如用基数排序替代比较排序。3.2 第四题动态规划入门第四题是一道动态规划题题目描述是给定一个数组要求找出一个最长的子序列使得子序列中相邻元素的差的绝对值不超过k。这道题的状态定义比较直接dp[i]表示以第i个元素结尾的最长子序列长度转移方程是dp[i] max(dp[j]) 1其中j i且|a[i] - a[j]| k。直接实现的话时间复杂度是O(n^2)如果n达到10的5次方这个复杂度会超时。优化思路是用线段树或者树状数组维护区间最大值。具体来说因为元素的值域可能很大需要先离散化然后对于每个a[i]查询值域在[a[i]-k, a[i]k]范围内的最大dp值再用这个值更新dp[i]最后把dp[i]插入到a[i]对应的位置。#include iostream #include vector #include algorithm using namespace std; const int MAXN 100005; int tree[MAXN * 4]; void update(int node, int l, int r, int pos, int val) { if (l r) { tree[node] max(tree[node], val); return; } int mid (l r) / 2; if (pos mid) update(node * 2, l, mid, pos, val); else update(node * 2 1, mid 1, r, pos, val); tree[node] max(tree[node * 2], tree[node * 2 1]); } int query(int node, int l, int r, int ql, int qr) { if (ql r || qr l) return 0; if (ql l r qr) return tree[node]; int mid (l r) / 2; return max(query(node * 2, l, mid, ql, qr), query(node * 2 1, mid 1, r, ql, qr)); } int main() { int n, k; cin n k; vectorint a(n); vectorint sorted_a; for (int i 0; i n; i) { cin a[i]; sorted_a.push_back(a[i]); } sort(sorted_a.begin(), sorted_a.end()); sorted_a.erase(unique(sorted_a.begin(), sorted_a.end()), sorted_a.end()); int m sorted_a.size(); int ans 0; for (int i 0; i n; i) { int pos lower_bound(sorted_a.begin(), sorted_a.end(), a[i]) - sorted_a.begin() 1; int left lower_bound(sorted_a.begin(), sorted_a.end(), a[i] - k) - sorted_a.begin() 1; int right upper_bound(sorted_a.begin(), sorted_a.end(), a[i] k) - sorted_a.begin(); int best query(1, 1, m, left, right); int cur best 1; ans max(ans, cur); update(1, 1, m, pos, cur); } cout ans endl; return 0; }注意动态规划题的难点往往不在状态转移方程本身而在于如何优化。比赛时先写出O(n^2)的暴力版本确认思路正确后再考虑用数据结构优化。这道题还有一个细节离散化之后查询区间[a[i]-k, a[i]k]对应的下标范围需要用lower_bound和upper_bound来确定。如果k很大导致查询范围覆盖整个值域那线段树查询就是O(log n)整体复杂度还是可以接受的。4. 压轴题组思维与代码能力的双重考验4.1 第五题图论建模与最短路变形第五题是一道图论题题目背景是给定一个无向图每条边有一个权值现在要求找一条从起点到终点的路径使得路径上边权的最大值最小。这道题是经典的最小瓶颈路问题可以用最小生成树或者二分答案加BFS来解决。最小生成树的思路是先对整个图跑一遍Kruskal算法构建最小生成树然后在最小生成树上找起点到终点的路径路径上的最大边权就是答案。为什么这样是对的因为最小生成树有一个性质任意两点之间的路径上的最大边权是所有可能路径中最小的。这个性质可以用反证法证明这里不展开。二分答案的思路是二分最大边权的值然后只保留边权不超过该值的边判断起点和终点是否连通。如果连通说明答案可以更小否则答案需要更大。这个思路更直观但时间复杂度是O(m log m log W)其中W是边权的最大值。#include iostream #include vector #include algorithm #include queue using namespace std; struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; vectorint parent; int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } bool unite(int x, int y) { int rx find(x), ry find(y); if (rx ry) return false; parent[rx] ry; return true; } int main() { int n, m; cin n m; vectorEdge edges(m); for (int i 0; i m; i) { cin edges[i].u edges[i].v edges[i].w; } sort(edges.begin(), edges.end()); parent.resize(n 1); for (int i 1; i n; i) parent[i] i; vectorvectorpairint, int mst(n 1); for (int i 0; i m; i) { if (unite(edges[i].u, edges[i].v)) { mst[edges[i].u].push_back({edges[i].v, edges[i].w}); mst[edges[i].v].push_back({edges[i].u, edges[i].w}); } } int start, end; cin start end; queueint q; vectorbool visited(n 1, false); vectorint maxEdge(n 1, 0); q.push(start); visited[start] true; while (!q.empty()) { int u q.front(); q.pop(); for (auto [v, w] : mst[u]) { if (!visited[v]) { visited[v] true; maxEdge[v] max(maxEdge[u], w); q.push(v); } } } cout maxEdge[end] endl; return 0; }提示图论题的关键是建模。把实际问题抽象成图之后很多看似复杂的问题就变成了经典模型。平时多积累经典模型和对应的解法比赛时能省很多时间。这道题还有一个变种如果要求的是路径上边权的最小值最大那就是最大瓶颈路问题可以用最大生成树来解决。思路完全对称只需要把排序顺序反过来即可。4.2 第六题组合数学与容斥原理第六题是一道组合计数题题目大意是给定n个元素要求选出k个元素使得这k个元素中至少有一个满足特定条件。直接算的话情况比较多容易漏算或者重复计算。这时候容斥原理就派上用场了。容斥原理的核心思想是先算所有情况的总数然后减去不满足条件的情况数再加回多减的部分以此类推。具体到这道题可以先算从n个元素中选k个的总数C(n, k)然后减去一个满足条件的都没有的情况数也就是从n - m个不满足条件的元素中选k个的数量C(n - m, k)其中m是满足条件的元素个数。#include iostream using namespace std; const int MOD 1e9 7; const int MAXN 100005; long long fact[MAXN], invFact[MAXN]; long long power(long long base, long long exp) { long long result 1; while (exp 0) { if (exp 1) result result * base % MOD; base base * base % MOD; exp 1; } return result; } void init() { fact[0] 1; for (int i 1; i MAXN; i) { fact[i] fact[i - 1] * i % MOD; } invFact[MAXN - 1] power(fact[MAXN - 1], MOD - 2); for (int i MAXN - 2; i 0; i--) { invFact[i] invFact[i 1] * (i 1) % MOD; } } long long C(int n, int k) { if (k 0 || k n) return 0; return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD; } int main() { init(); int n, m, k; cin n m k; long long total C(n, k); long long none C(n - m, k); long long ans (total - none MOD) % MOD; cout ans endl; return 0; }注意组合数学题一定要注意取模运算。减法操作要加上MOD再取模避免出现负数。另外预处理阶乘和逆元的时候数组大小要开够否则会越界。这道题的难点在于理解容斥原理的应用场景。如果题目条件更复杂比如“至少满足两个条件”就需要用更一般的容斥公式枚举所有可能的条件组合根据组合的大小决定是加还是减。4.3 第七题数据结构综合应用第七题是压轴题考察的是多种数据结构的综合应用。题目大意是维护一个序列支持三种操作单点修改、区间查询最大值、区间查询历史最大值。这道题需要用到线段树而且每个节点要维护多个信息当前最大值、历史最大值、当前懒标记、历史最大懒标记。线段树维护历史最大值的核心思想是在pushdown的时候不仅要更新子节点的当前最大值还要用父节点的历史最大懒标记去更新子节点的历史最大值。具体来说每个节点维护四个值maxVal当前区间最大值、maxHistory历史区间最大值、lazyAdd当前加法懒标记、lazyAddHistory历史最大加法懒标记。#include iostream #include algorithm using namespace std; const int MAXN 100005; const int INF 1e9; struct Node { int maxVal; int maxHistory; int lazyAdd; int lazyAddHistory; } tree[MAXN * 4]; int a[MAXN]; void pushUp(int node) { tree[node].maxVal max(tree[node * 2].maxVal, tree[node * 2 1].maxVal); tree[node].maxHistory max(tree[node * 2].maxHistory, tree[node * 2 1].maxHistory); } void pushDown(int node) { for (int child node * 2; child node * 2 1; child) { tree[child].maxHistory max(tree[child].maxHistory, tree[child].maxVal tree[node].lazyAddHistory); tree[child].lazyAddHistory max(tree[child].lazyAddHistory, tree[child].lazyAdd tree[node].lazyAddHistory); tree[child].maxVal tree[node].lazyAdd; tree[child].lazyAdd tree[node].lazyAdd; } tree[node].lazyAdd 0; tree[node].lazyAddHistory 0; } void build(int node, int l, int r) { tree[node].lazyAdd 0; tree[node].lazyAddHistory 0; if (l r) { tree[node].maxVal a[l]; tree[node].maxHistory a[l]; return; } int mid (l r) / 2; build(node * 2, l, mid); build(node * 2 1, mid 1, r); pushUp(node); } void update(int node, int l, int r, int ql, int qr, int val) { if (ql r || qr l) return; if (ql l r qr) { tree[node].maxVal val; tree[node].lazyAdd val; tree[node].maxHistory max(tree[node].maxHistory, tree[node].maxVal); tree[node].lazyAddHistory max(tree[node].lazyAddHistory, tree[node].lazyAdd); return; } pushDown(node); int mid (l r) / 2; update(node * 2, l, mid, ql, qr, val); update(node * 2 1, mid 1, r, ql, qr, val); pushUp(node); } int query(int node, int l, int r, int ql, int qr) { if (ql r || qr l) return -INF; if (ql l r qr) return tree[node].maxHistory; pushDown(node); int mid (l r) / 2; return max(query(node * 2, l, mid, ql, qr), query(node * 2 1, mid 1, r, ql, qr)); } int main() { int n, m; cin n m; for (int i 1; i n; i) cin a[i]; build(1, 1, n); while (m--) { int op, l, r, val; cin op; if (op 1) { cin l r val; update(1, 1, n, l, r, val); } else { cin l r; cout query(1, 1, n, l, r) endl; } } return 0; }提示线段树维护历史最大值是进阶内容比赛时如果遇到建议先在纸上把pushdown的逻辑理清楚确认每个变量的更新顺序正确后再写代码。顺序错了的话调试起来非常痛苦。这道题的时间复杂度是O((n m) log n)对于10的5次方级别的数据规模完全可以接受。但代码量比较大比赛时要注意写完后用样例验证确保没有漏掉pushdown或者pushup。5. 比赛策略与团队协作经验5.1 开题顺序与时间分配团队赛和单人赛最大的区别在于三个人可以同时开不同的题。但开题顺序有讲究建议先花5到10分钟把所有的题目快速浏览一遍标记出每道题的预估难度和类型。然后按照“签到题—中档题—压轴题”的顺序分配人手。通常的做法是一个人负责签到题尽快AC拿到罚时优势另一个人负责中档题中自己最擅长的类型第三个人负责压轴题的读题和建模。时间分配上签到题控制在15分钟以内中档题每道控制在40到60分钟压轴题留出至少一个小时。如果某道题卡了超过30分钟还没有明确思路建议换人看或者先跳过避免全队卡在一道题上。5.2 代码风格与调试技巧团队赛中代码是三个人共享的所以代码风格要统一。建议赛前就约定好变量命名规则、缩进风格、常用宏定义等。这样队友看你的代码时不会因为风格差异而浪费时间。调试技巧方面最有效的方法是“小数据对拍”。写一个暴力解法随机生成小规模测试数据对比两个程序的输出。如果结果不一致就找到了反例可以针对性地分析。另外善用assert和打印中间变量但记得提交前删掉或者注释掉避免输出多余内容导致WA。5.3 常见失分点与避坑指南根据这次比赛的情况我整理了几个常见的失分点用表格列出来方便对照失分点典型表现避坑方法数据范围没看清用int存了10的9次方以上的数读题时先把所有变量的范围标注出来边界条件遗漏n0或n1时程序崩溃写完代码后手动测试最小和最大规模多组输入处理不当只处理了一组数据确认题目是否有多组输入用while循环输出格式错误多了空格或少了换行复制样例输出对比注意行末空格数组越界线段树开小了根据数据范围计算所需数组大小留足余量取模运算出错减法后出现负数减法后加MOD再取模贪心策略错误没有证明就提交用小数据对拍验证贪心正确性注意比赛时提交前一定要用样例测试一遍确认输出和样例完全一致。很多WA都是因为输出格式不对而不是算法错误。6. 从题解到实战如何高效训练6.1 按专题刷题的正确姿势看完题解之后最重要的是自己动手实现一遍。但不要只是照着题解抄代码而是要先理解思路然后关掉题解自己写。如果写不出来再回去看题解分析自己卡在了哪一步。是状态定义没想到还是转移方程写错了还是数据结构不会用找到薄弱环节后针对性地刷同类型的题目。建议按专题来训练比如这一周专门刷贪心题下一周专门刷动态规划题。每个专题刷10到15道题从简单到困难逐步提升。刷题时要注意总结套路比如贪心题常见的证明方法、动态规划题常见的状态定义方式等。6.2 团队配合的模拟训练团队赛的配合需要专门训练。建议每周至少进行一次模拟赛完全按照比赛规则来三个人共用一台电脑限时5小时题目从历年真题中随机抽取。模拟赛后要复盘哪些题浪费了时间沟通是否顺畅代码是否出现了冲突通过反复模拟找到最适合你们队伍的协作模式。6.3 赛后复盘的正确方法比赛结束后不要只看自己过了几道题而是要把没过的题都补上。对于每道没过的题问自己三个问题比赛时为什么没做出来是知识点不会还是思路没打开如果下次遇到类似的题应该怎么思考把这三个问题的答案写下来形成自己的“错题本”。下次比赛前翻一翻能避免很多重复的错误。我个人在实际训练中的体会是题解看得再多不如自己亲手写一遍。看题解的时候觉得“我懂了”但真正写代码的时候才会发现各种细节问题。所以看完这篇题解之后建议你打开编译器把每道题的代码自己敲一遍提交到对应的评测平台上验证。只有通过了所有测试点才算真正掌握了这道题。