企业官网建设流程全解析

平时带训练队和帮人改简历时，被问得最多的一个问题是：刷了几百道题还是没底，竞赛来了照样不会做，到底哪里出了问题？

问得多了，我发现这背后其实有个共性的误解——很多人把“刷题量”当成了“能力值”，但竞赛比的根本不是谁见过的题多，而是谁能在有限时间内认出题目的本质、调出对应的套路。换句话说，高频题型的识别能力和模板的熟练度，才决定你是省奖还是国奖。

这篇文章把竞赛里最常出现的题型按“入门→进阶”梯度做个完整梳理，每一类都给出通用代码模板、复杂度分析、LeetCode同源题对照，以及我在实战里真正踩过的坑。内容偏向那些刚打完基础题、开始做套题的选手，也适合中期想系统捋一遍知识框架的人。

1. 先从整体框架说起：竞赛题到底在考什么

很多初学者有个错觉，以为竞赛题天马行空、什么怪题都有。实际上，命题是有规律可循的。把每年各类比赛的题目拆开来看，你会发现核心考点的出现频率极其稳定，基本集中在下面这张表里。

这里的启发很明显：如果你目标是稳拿铜牌或省二，入门和基础部分的题必须全对，进阶部分能拿一半就行。所以你看，认识题型这件事，本质上是帮你把有限的备赛时间花在得分效率最高的地方。

我建议准备竞赛的选手做这样一件事：把近三年的真题按“考点标签”而不是“题目顺序”重新整理一遍。同一考点的题放一起，你很快就能发现套路是如何反复出现的。

1.1 高频题型识别术：拿到题先问自己三个问题

拿到一道题，先别急着敲代码。我习惯让队员在读题后30秒内完成三步判断——这比任何技巧都重要：

• 这道题隐藏了什么数据结构的影子？比如“区间和”“区间更新”就指向线段树或前缀和，“最近公共祖先”就指向LCA。
• 数据范围允许什么复杂度？n ≤ 10的五次方就不可能用O(n²)，说明必须二分或O(n)扫描；n ≤ 20大概率是搜索或状态压缩DP。
• 有没有经典的“题眼”关键词？比如“最大化最小值”基本就是二分答案，“至少需要几次”多半是BFS最短路。

第三步最关键也最容易被忽略。题眼词和算法之间的对应关系，是竞赛里最值钱的经验。下面这张表是我在训练时总结的，打印出来贴在电脑边也不为过。

别小看这个表，它能帮你在赛场上省下大量犹豫时间。很多时候，选手做不完题不是因为不会，而是因为判断这道题用了太久。

2. 入门必会五大题型：这些题必须拿满分

2.1 模拟题：别轻敌，细节才是区分度

模拟题看起来谁都能做，但为什么有些人AC有些人卡一整场？因为模拟题的考点就是代码实现的鲁棒性。

说穿了，模拟题就是按照题目描述一步步做，难的是边界条件的处理。比如日期计算，或者矩阵旋转，这些题出错的地方往往不在中间过程，而在最后一步。

拿矩阵顺时针旋转90度来说，核心操作是先转置再左右翻转，这个模板请直接背下来：

void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); // 第一步：沿对角线转置 for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { swap(matrix[i][j], matrix[j][i]); } } // 第二步：每行左右翻转 for (int i = 0; i < n; i++) { reverse(matrix[i].begin(), matrix[i].end()); } }

模拟题的坑大多集中在循环边界、数组越界和类型溢出这三处。我的建议是：任何模拟题，写完先手动跑一遍样例，再把n=1、n=max这些极端情况各测一遍，再提交。这个过程看起来浪费时间，其实能帮你避免几次毫无意义的罚时。

LeetCode同源题：48题旋转图像，54题螺旋矩阵，59题螺旋矩阵II，498题对角线遍历。这几道选两道练手就够了，重点感受一下边界条件的处理节奏。

2.2 前缀和与差分：区间操作的两把快刀

前缀和解决的是“多次询问区间和”的问题，核心思想一句话：预处理出所有前i项的和，任意区间和等于两项之差。

vector<int> prefixSum(vector<int>& nums) { int n = nums.size(); vector<int> pre(n + 1, 0); for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] + nums[i]; } return pre; } // 查询区间 [l, r] 的和 = pre[r+1] - pre[l]

这个模板简单到不能再简单，但威力巨大。为什么？因为它把O(n)的区间查询降到了O(1)。当题目里出现“m次区间查询”这类字眼时，前缀和基本就是标准答案。

这里我要特别讲一个容易被忽略的东西——差分。前缀和解决区间和查询，差分解决区间同时加上一个数的操作。两者其实是互为逆运算的关系。

差分数组d[i] = a[i] - a[i-1]，对区间[l,r]统一加x，只需要d[l] += x, d[r+1] -= x，最后做一遍前缀和还原即可。这个技巧在竞赛里出场率极高，尤其是配合排序的区间覆盖类题目。

实测感受：我见过不少学了一个月的选手，遇到“给定n个区间操作，求每个位置的值”这种题时，还会老老实实写个循环逐区间更新，结果数据一大就TLE。这不是能力问题，是脑子里少挂了一个“区间操作”的钩子——当你看到“多次区间加”、“区间覆盖”这些词，第一反应就应该是差分。

LeetCode同源题：303题区域和检索，304题二维区域和检索，1109题航班预订统计（这道就是纯差分裸题），370题区间加法。

2.3 双指针：把O(n²)降成O(n)的魔法

双指针的核心思想并不复杂：利用单调性，让两个指针各自只朝一个方向移动，从而避免重复扫描，达到线性复杂度。

最常见的应用场景，是有序数组上的两数之和问题。之前用两层循环是O(n²)，但有序数组配双指针，可以将复杂度降到O(n)。

vector<int> twoSum(vector<int>& nums, int target) { int l = 0, r = nums.size() - 1; while (l < r) { int sum = nums[l] + nums[r]; if (sum == target) return {l, r}; else if (sum < target) l++; else r--; } return {}; }

为什么双指针一定正确？关键在于有序性带来的单调关系——左指针右移时和增大，右指针左移时和减小，这就保证了每一步的移动方向是唯一确定的，不存在漏解。

双指针还有一大变体是滑动窗口，专门解决“满足某条件的最短/最长连续子数组”问题。最典型的模板是维护一个窗口，右指针扩展、左指针收缩，中间用一个哈希表或计数器记录窗口状态。

// 找最短包含t中所有字符的子串长度 int lengthOfLongestSubstring(string s) { vector<int> cnt(128, 0); int l = 0, ans = 0; for (int r = 0; r < s.size(); r++) { cnt[s[r]]++; while (cnt[s[r]] > 1) { // 有重复就收缩 cnt[s[l]]--; l++; } ans = max(ans, r - l + 1); } return ans; }

这个模板很经典，做字符串子串相关题目时可以反复用。

坑提醒：双指针题目最容易出错的，是循环终止条件的判断。到底是l < r还是l <= r？建议每次都拿空数组、单元素数组测一下，形成肌肉记忆。

LeetCode同源题：167题两数之和II、3题无重复字符的最长子串、76题最小覆盖子串、209题长度最小的子数组。这四题建议都做，因为滑动窗口和双指针的配合场景在竞赛里出场率极高。

2.4 二分答案：把最优化问题变成判定问题

这是我最想强调的一个模板，因为它是竞赛入门选手升级的一个重要分水岭。

很多题目问的是“最小化最大值”或“最大化最小值”，比如“在m天内运完所有货物，求最小运力”“划分成k段，求各段和最大值的最小值”。这种题直接求很难，但如果你反过来问：给定一个答案x，能不能做到？就变成了一个极其简单的贪心判定——多简单呢？最粗暴的写法就是按顺序扫一遍数数即可。

这种思路，就是二分答案。它的通用模板：

bool check(int x) { // 判断答案x是否可行，根据题目实现 // 返回值：x可行返回true，否则返回false } int binarySearch(int left, int right) { while (left < right) { int mid = (left + right) / 2; if (check(mid)) right = mid; // 如果mid可行，尝试更小的 else left = mid + 1; } return left; }

模板看似简单，但有两个容易错的点：

第一个，mid的计算方式。用(left + right) / 2在left+right很大会溢出，建议写成left + (right - left) / 2。这个细节比赛里经常见选手翻车。

第二个，边界更新时的左闭右开问题。模板里用的是right = mid和left = mid + 1，这是“可行域最小值”的写法；但如果题目要求的是“最大值”，循环条件和更新逻辑就要反过来。

经验分享：初学者练二分答案，建议先别急着看题解，而是先训练自己把原题改写成“给定x，判断是否能做到”的check函数。这一步完成了，剩下的就是套模板。

一套二分复杂度是O(logM)，其中M是答案范围，check是O(n)的话，总复杂度就是O(n logM)，对于n ≤ 10⁵的数据范围完全够用。

LeetCode同源题：1011题在D天内送达包裹的能力、410题分割数组的最大值、875题爱吃香蕉的珂珂。这三题是二分答案的三胞胎，做完你会彻底理解这个套路。

2.5 贪心算法：难在证明，容易在写代码

贪心的代码往往20行就搞定了，但很多选手却不敢写，因为怕贪错了。这里给大家一个定心丸：竞赛里的贪心题，大多数都带着“排序”这个前置操作。

排序后贪心，是最经典的套路组合。比如“给一堆会议时间，选尽量多的会议参加”，按结束时间排序后能选就选，这就是最优解。

int maxEvents(vector<vector<int>>& events) { sort(events.begin(), events.end(), [](auto&a, auto&b) { return a[1] < b[1]; // 按结束时间升序 }); int lastEnd = -1, ans = 0; for (auto& ev : events) { if (lastEnd < ev[0]) { // 当前会议可以和上一个共存 ans++; lastEnd = ev[1]; } } return ans; }

关于贪心证明这个问题，我的观点是：初学者不需要每次都会严格证明，但必须有意识地用“反例测试”来验证方案。写完之后，尝试构造一个能推翻自己贪心策略的例子，如果找不到，这个策略大概率是对的。

LeetCode同源题：435题无重叠区间、452题用最少数量的箭引爆气球、55题跳跃游戏、134题加油站。这些题都带着“排序+贪心”的味道，适合一起刷。

3. 进阶必会六类题：有区分度的题型都在这

3.1 BFS最短路：图上的扩散问题

BFS的模板非常固定，所有“最少步数”“最短路径”“扩散次数”类问题都能套：

int bfs(vector<vector<int>>& grid, int sx, int sy) { int n = grid.size(), m = grid[0].size(); int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; queue<pair<int, int>> q; vector<vector<bool>> vis(n, vector<bool>(m, false)); q.push({sx, sy}); vis[sx][sy] = true; int steps = 0; while (!q.empty()) { int sz = q.size(); while (sz--) { // 按层出队 auto [x, y] = q.front(); q.pop(); if (满足目标条件) return steps; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && grid[nx][ny] != 障碍) { vis[nx][ny] = true; q.push({nx, ny}); } } } steps++; } return -1; // 不可达 }

这里最关键的一步是在入队时标记访问，而不是出队时标记。很多新手习惯出队时标记访问，结果同一个节点被重复入队多次，内存和速度双双爆炸，还可能死循环。这个坑我在带新人时几乎每次都会遇到。

扩展思路：如果边权不都为1，比如有些格子走一步代价是5，就用Dijkstra；如果边权只有0和1，用01-BFS（双端队列，0权重放队首，1权重放队尾）。这两者都是BFS的进阶版，竞赛里出现的频率也不低。

LeetCode同源题：200题岛屿数量、279题完全平方数、994题腐烂的橘子、1162题地图分析。这些题做完，BFS的骨架应该就能牢牢掌握了。

3.2 树的遍历与递归：二叉树模板必须烂熟于心

树的题在竞赛里以中档题为主，区分度主要体现在你能不能把递归逻辑写清楚。下面这个三段式是所有二叉树题的通用框架：

// 前序遍历 void traversal(TreeNode* root) { if (!root) return; // 终止条件 visit(root); // 访问操作 traversal(root->left); // 左子树 traversal(root->right); // 右子树 }

三种遍历的唯一区别，就是visit(root)这行代码所在的位置。放最前面是前序，放中间是中序，放最后是后序。这个框架能解决绝大多数递归树题。

进阶应用：当你遇到“树的最大路径和”“树的最近公共祖先”“树形DP”这些题时，本质上都是在递归遍历的过程中，利用返回值传递信息。比如，求二叉树最大深度，返回值就是子树深度加一：

int maxDepth(TreeNode* root) { if (!root) return 0; return 1 + max(maxDepth(root->left), maxDepth(root->right)); }

树形DP是竞赛中的一个重要进阶考点，核心思路是把dp数组定义在树节点上，通过递归回溯时合并子节点的状态。经典题目如“打家劫舍III”“树的最长直径”都属于这个范畴。

LeetCode同源题：104题最大深度、226题翻转二叉树、110题平衡二叉树、543题二叉树的直径、236题最近公共祖先、337题打家劫舍III（经典树形DP入门题）。

3.3 DFS回溯：当搜素状态空间不大时，这就是暴力美学

DFS回溯本质上是穷举所有可能路径，只是在走不通时提前返回（剪枝），避免无效搜索。

大多数用DFS的题目，可以统一成这样一个模板：

void dfs(当前状态, 路径记录) { if (满足结束条件) { 保存一个可行解; return; } for (每个可能的下一步选择) { if (选择不合法) continue; 做选择; dfs(更新后的状态, 更新后的路径); 撤销选择; // 回溯 } }

回溯最难理解的点在于“撤销选择”这一步，也就是为什么递归结束之后要把状态改回去。这个机制可以这样理解：所有递归分支共享同一份状态数组，如果不撤销，上一条分支的修改就会“污染”下一条分支的计算结果。

看一个全排列的经典例子：

void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& ans) { if (path.size() == nums.size()) { ans.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { if (used[i]) continue; used[i] = true; path.push_back(nums[i]); dfs(nums, used, path, ans); path.pop_back(); used[i] = false; } }

重要提醒：DFS题目最关键的是评估状态空间的大小。如果状态数在百万级别以内，DFS随便跑；如果超过千万，就必须上剪枝或换算法了。盲目写DFS而忽略状态空间，是很多选手TLE的根本原因。

LeetCode同源题：46题全排列、78题子集、39题组合总和、79题单词搜索、51题N皇后。前四题是最经典的“组合模板”，建议至少做两遍。

3.4 动态规划入门：状态定义这一步做对了，题目就对了一半

DP难不在转移方程，难在状态定义。很多人卡住，是因为一开始状态就定义歪了。

两件事先搞清楚：dp[i]代表什么？从dp[j]怎么推出dp[i]？

最经典的上楼梯：dp[i] = dp[i-1] + dp[i-2]，表示到第i级的方法数等于到i-1和i-2级的方法数之和。这个例子看起来简单，但它揭示了DP的本质：当前状态由之前的某些状态转移而来。

所有DP都用这个模板：

vector<int> dp(n, 0); dp[0] = 初始值; // 初始化边界 for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { // 枚举可转移的前驱状态 dp[i] = max(dp[i], dp[j] + 转移代价); } } return dp[n-1];

入门阶段，先练两类DP就足够：

第一种：线性DP。特点是状态数组是一维的，转移依赖前面某个位置的状态。典型题目如最大子序和、最长递增子序列——后者是竞赛中的“常青树”。

int lengthOfLIS(vector<int>& nums) { int n = nums.size(), ans = 1; vector<int> dp(n, 1); // dp[i]表示以nums[i]结尾的最长递增子序列长度 for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); ans = max(ans, dp[i]); } } } return ans; }

第二种：背包DP。0-1背包和完全背包是竞赛的绝对热门，模板务必背熟：

// 0-1背包：每个物品只能用一次 for (int i = 1; i <= n; i++) { for (int w = capacity; w >= weight[i]; w--) { dp[w] = max(dp[w], dp[w - weight[i]] + value[i]); } } // 完全背包：每个物品不限次数 for (int i = 1; i <= n; i++) { for (int w = weight[i]; w <= capacity; w++) { dp[w] = max(dp[w], dp[w - weight[i]] + value[i]); } }

有个细节值得注意：0-1背包的内层循环是逆序的，完全背包是正序的。原因很简单——逆序防止一个物品被重复选取，正序则允许重复选取。这个细微差别背后是两种完全不同的算法语义，理解了这一点，背包题基本就通了。

LeetCode同源题：70题爬楼梯、198题打家劫舍、300题最长递增子序列、322题零钱兑换、416题分割等和子集（0-1背包裸题）、518题零钱兑换II（完全背包裸题）。

3.5 拓扑排序：有依赖关系的顺序问题

当题目中出现“先修课”“依赖关系”“先后顺序”这样的字眼时，基本可以锁定拓扑排序。

拓扑排序的核心思想很朴素：不断找出当前入度为0的节点，把它放进结果序列，然后去掉它所有出边（即减少邻居入度）。如果最终结果节点数不等于总节点数，说明图中存在环，问题无解。

vector<int> topoSort(int n, vector<vector<int>>& edges) { vector<vector<int>> g(n); vector<int> inDeg(n, 0); for (auto& e : edges) { g[e[0]].push_back(e[1]); inDeg[e[1]]++; } queue<int> q; for (int i = 0; i < n; i++) { if (inDeg[i] == 0) q.push(i); } vector<int> ans; while (!q.empty()) { int u = q.front(); q.pop(); ans.push_back(u); for (int v : g[u]) { if (--inDeg[v] == 0) q.push(v); } } if (ans.size() != n) return {}; // 存在环 return ans; }

这个算法有个看似微小但很重要的点：入队的节点顺序。如果要求字典序最小的拓扑序，把queue换成priority_queue即可。很多题目在这一点上做文章，所以模板里建议把容器位置留出来，视题目要求替换。

LeetCode同源题：207题课程表、210题课程表II、802题找到最终的安全状态。这三题做完，拓扑排序就能应付绝大多数情况了。

3.6 最短路算法：Dijkstra模板及优化

图论题里最短路是重中之重，竞赛中的常见场景是“带权图求最少代价路径”。如果所有边权非负，就用Dijkstra；存在负权边，用SPFA或Bellman-Ford。竞赛里前者出现的次数远超后者。

Dijkstra + 优先队列（堆优化）的模板是目前的主流写法，复杂度O(E log V)，对大多数数据范围够用：

vector<int> dijkstra(int n, vector<vector<pair<int,int>>>& g, int s) { vector<int> dist(n, INT_MAX); dist[s] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; // 跳过旧最短路径 for (auto [v, w] : g[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } return dist; }

这里有一个值得说明的细节：if (d > dist[u]) continue这个判断本质上是一次懒删除，跳过已经过时的队列记录。没有这行代码，算法虽然慢点但结果依然正确；有这行代码，性能提升非常明显。很多初学者不理解为何已经入队过的节点还会重复入队，因为有更新的dist[v]更新时就会再push一次，所以同一个节点可能在队列里出现多次，配合优先队列只会优先处理最短的那个。

实际教训：在带新人的过程中我发现，最短路题最常出的错不是Dijkstra本身，而是建图时忽略重边和自环。题目没说没有重边，你不处理，就会得到错误答案。建图时直接取最小值即可，这个习惯请尽早养成。

LeetCode同源题：743题网络延迟时间（纯Dijkstra裸题）、1514题概率最大的路径（乘法版最短路）、1631题最小体力消耗路径（可用二分+Dijkstra，进阶题）。

4. 高频考点的进阶变体：走到这一步已经有了拿牌实力

4.1 状态压缩DP：小数据范围的暴力最优解

当题目数据范围中出现n ≤ 20这种小而明确的限制时，大概率就是状态压缩DP的信号。核心思路：用一个整数的二进制位表示一个集合的状态，dp[mask]表示处于该状态时的最优值。

比如经典的旅行商问题，dp[mask][i]表示已经访问过的城市集合为mask，当前在城市i时的最短路径：

int dp[1<<n][n]; for (int mask = 1; mask < (1<<n); mask++) { for (int i = 0; i < n; i++) { if (!(mask & (1<<i))) continue; // 当前不包含城市i // 从上一个包含城市j的状态转移过来 } }

这类题的关键在于用位运算快速判断状态转移的合法性。常用的几个位运算要滚瓜烂熟：判断第i位是否为1用mask & (1<<i)，设置第i位为1用mask | (1<<i)，去掉第i位用mask ^ (1<<i)，枚举mask的所有非空子集用sub = (sub-1) & mask。

LeetCode同源题：526题优美的排列、691题贴纸拼词、847题访问所有节点的最短路径。这三题由简到难，第一题比较适合作为状态压缩的入门体验。

4.2 线段树进阶：区间操作的最强通用解

线段树是竞赛中的重量级选手，能处理所有区间类问题——区间求和、区间最大值、区间加、区间赋值、区间合并等等。它本质上是一棵完全二叉树，每个节点对应一段区间，通过递归完成操作。

线段树的代码量比之前所有模板都大，但这套模板值得熟记。一个支持“区间加 + 区间求和”的简化版：

struct SegTree { vector<long long> sum, lazy; vector<int> nums; int n; SegTree(vector<int>& arr) { n = arr.size(); nums = arr; sum.resize(4*n); lazy.resize(4*n); build(1, 0, n-1); } void build(int node, int l, int r) { if (l == r) { sum[node] = nums[l]; return; } int mid = (l+r)>>1; build(node<<1, l, mid); build(node<<1|1, mid+1, r); sum[node] = sum[node<<1] + sum[node<<1|1]; } void pushDown(int node, int l, int r) { if (lazy[node] == 0) return; int mid = (l+r)>>1; int leftChild = node<<1, rightChild = node<<1|1; lazy[leftChild] += lazy[node]; lazy[rightChild] += lazy[node]; sum[leftChild] += lazy[node] * (mid - l + 1); sum[rightChild] += lazy[node] * (r - mid); lazy[node] = 0; } void update(int node, int l, int r, int L, int R, long long val) { if (L <= l && r <= R) { lazy[node] += val; sum[node] += val * (r - l + 1); return; } pushDown(node, l, r); int mid = (l+r)>>1; if (L <= mid) update(node<<1, l, mid, L, R, val); if (R > mid) update(node<<1|1, mid+1, r, L, R, val); sum[node] = sum[node<<1] + sum[node<<1|1]; } long long query(int node, int l, int r, int L, int R) { if (L <= l && r <= R) return sum[node]; pushDown(node, l, r); int mid = (l+r)>>1; long long res = 0; if (L <= mid) res += query(node<<1, l, mid, L, R); if (R > mid) res += query(node<<1|1, mid+1, r, L, R); return res; } };

这里的pushDown是懒标记的核心：更新整个覆盖区间时，不往下层层修改，而是先记住这个节点的延期修改，等真正需要访问子节点时才把修改传递下去。这个技巧保证了每次区间操作的复杂度是O(log n)，而非O(n)。

建议：线段树是很多进阶题的“底层工具”，但没必要一开始就花一周死磕。我的训练顺序是：先把上一节的前缀和、差分、树状数组练熟，再上线段树，这样理解起来会顺畅得多。

LeetCode同源题：307题区域和检索（线段树入门）、699题掉落的方块（离散化+线段树，偏难）、1157题子数组中占绝大多数的元素（线段树+随机化）。

4.3 并查集：动态连通性问题的最佳解法

并查集解决的是“判断两个元素是否连通”的问题，配合路径压缩和按秩合并，均摊复杂度几乎O(1)。

为什么并查集在竞赛里高频出现？因为它把“无向图连通性判断”这一问题从反复DFS的O(nm)降到了接近线性的水平。

struct DSU { vector<int> fa, sz; DSU(int n) { fa.resize(n); sz.resize(n, 1); iota(fa.begin(), fa.end(), 0); // 初始时每个元素自成一族 } int find(int x) { if (fa[x] != x) fa[x] = find(fa[x]); // 路径压缩 return fa[x]; } void merge(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (sz[a] < sz[b]) swap(a, b); // 按大小合并 fa[b] = a; sz[a] += sz[b]; } };

实操心得：路径压缩用递归写简洁，但极端情况下（如下面节点特别深）有爆栈风险。如果你实现的环境对递归深度有严格限制，可以用迭代版本——先循环找出根节点，再沿路径把每个节点的fa直接指向根。我一直建议选手两种写法都掌握，平时用递归，特殊场合用迭代。

并查集的一些高级玩法还包括带权并查集（在合并时维护节点到根的权值差，用于处理元素之间相对关系的题目）和可撤销并查集（记录每一步操作，支持回退），后者配合离线分治能解决一类较难的区间查询问题。这部分如果时间充裕值得学一学。

LeetCode同源题：547题省份数量、684题冗余连接、721题账户合并、990题等式方程的可满足性。这四题覆盖了并查集的大部分基础用法，且难度平滑上升。

5. 通用模板与刷题路线：怎么练才能形成肌肉记忆

5.1 一套通用的竞赛代码模板

熟悉了各个题型以后，应该沉淀出一套自己的代码习惯。下面这份是我个人长期使用的C++竞赛开局模板，可以根据所需自行调整：

#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PII; // 快速读入输出（重要，能省不少时间） inline int readInt() { int x=0, f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x*f; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 解题代码 return 0; }

bits/stdc++.h编译速度在本地可能慢一点，但各大竞赛平台都支持，所以这个模板在赛场上直接可用。ios::sync_with_stdio(false); cin.tie(nullptr);这两行也是必写的，否则cin/cout在某些题目上会比scanf/printf慢很多，遇到大数据量的输入直接拖垮全题。

5.2 按题型的刷题路线（三轮学习法）

把上面的模板和题型用起来，我推荐“三轮刷题法”：

第一轮：看懂模板。把本文列出的每个模板抄一遍，一行一行读懂，自己跑通一个简单测试样例。这个阶段不用求快，重在理解每一行的意义。

第二轮：配套刷题。每类题型配合3-5道LeetCode同源题，先自己做，卡住了再看模板对应位置。做完这轮，应该能做到只花一两分钟就能想起来题型对应的核心思路。

第三轮：限时套卷。找一套近年的竞赛真题，按比赛时间限制完整做一遍。这一步的目的不是刷题，而是训练时间分配：哪些题该拿多少时间、做不出来时什么时候该放弃去保下一题。

刷题量到底要多少才够保奖？我给一个参考：入门阶段把每种题型刷满15题，核心题库500题左右，这个量对铜牌来说基本足够。再往上，量的边际效用就下降了，更多靠思维训练和套卷模拟经验。

5.3 训练中的常见思维误区

带新人的过程中，有三类误区出现频率最高，写了这么多模板，最后集中说说。

第一个误区是“模板背下来了，但没理解适用范围”。比如有人会拿双指针去处理未排序数组的两数之和，得到错误答案。模板始终是有限条件下成立的，使用前必须确认前提条件是否满足。

第二个误区是“算法复杂度分析不到位”。判断一道题能不能用O(n²)的算法，不只看n的大小，还要看时间限制和常数因子。同一道题在竞赛平台和LeetCode上的测评压力完全不同，习惯LeetCode宽松评测的选手，在正规赛场上很容易超时。

第三个误区最隐蔽，却影响最大：拿到新题先想“这是什么类型”。但很多题并不是纯种的单一类型，而是几种题型的叠加组合。比如“树的直径”既需要树的遍历基础，又需要两次BFS或树形DP；“接雨水”既是双指针，也是单调栈。我建议在掌握了单一模板之后，有意识地去练这些“缝合怪”题目，这才是真正的能力提升点所在。

6. 最后的经验总结：关于比赛节奏与心态的几条建议

很多技术上的东西说完了，但真正上赛场时会发现，技术之外的细节同样决定成败。这里说几条我自己实际比赛和带队总结出的心得。

第一，时间分配比刷题量更重要。我个人的比赛策略是：开赛后先花15分钟把六道题全部读完，给每道题标注预估难度和大致算法方向。然后按“做出一道签到题→冲击最有把握的中档题→再回头处理难题”的顺序推进。把最容易拿分的题留在最后做，是最亏的时间安排。

第二，罚时是隐形的排名杀手。竞赛里提交错误一次会有罚时加成，这意味着你提交一个不AC的代码，实际代价比你以为的更大。所以提交前务必自己多测几组数据。现场赛不像LeetCode有多次提交机会，这个问题更加尖锐。

第三，模板只是基础，现场才是真正综合能力的检验。建议在赛前几天，不依赖模板库里查注释，闭卷默写一遍最常用的几个模板——线段树、Dijkstra、拓扑排序、最长递增子序列。能默写出来，才算真正内化。不能默写出来，就说明还停留在“看懂”的层面，离“随时调用”还有距离。

竞赛这条路的吸引力，正在于它让你反复体验到“原来这个看似复杂的问题，拆解之后不过就是一个已知模板+一点组合变形”。希望这篇题型总结能帮你在赛前把知识框架理清楚，找到自己最值得突破的那个方向。