信奥必会算法Top10：不会这些别说你打过比赛

在信息学竞赛（NOI/ACMICPC/CSP）的赛场上，算法是解题的武器库。无论你是刚学完语法的新手，还是卡在瓶颈期的选手，对核心算法的理解深度直接决定了你的奖牌成色。

结合近年出版的《算法竞赛入门笔记》《算法设计与分析》以及多位金牌选手的经验，今天我们来盘点信息学竞赛中十大必会算法。这不仅是入门基石，更是冲击高分的关键。如果不熟练掌握这些，确实很难说自己真正“打过比赛”。

第1名：暴力枚举与模拟 —— 永不落幕的“基本盘”

核心思想：“暴力出奇迹” 是竞赛圈的第一句黑话。枚举（Enumeration）就是穷举所有可能，而模拟（Simulation）则是忠实遵循题目步骤，不加入复杂的数学优化，用代码“复刻”过程。

为什么必会：哪怕是最简单的题目，也离不开模拟。而在骗分策略中，对于不会做的难题，通过暴力枚举获取部分分数（部分分），是每个选手必须掌握的生存技能。

实战技巧：2024年CSP认证的第4题“十滴水”，虽然数据范围极大，但选手仍需结合map离散化和优先队列来模拟水滴爆炸的过程。纯暴力不可取，但“模拟+数据结构优化”是高频考点。

第2名：二分与分治 —— 以“减半”制胜

核心思想：分治（Divide and Conquer）将大问题拆成结构相似的子问题，递归解决后合并结果。二分（Binary Search）则是在单调有序空间内，每次将搜索范围减半。

经典案例：

• 二分答案：如“砍树问题”（洛谷P1873）、“进击的奶牛”（洛谷P1824），当直接求解困难时，转而判断“当前答案是否可行”。

• 归并排序：不仅是排序，更是求逆序对（洛谷P1908）的经典解法。

第3名：贪心算法 —— 局部最优即全局最优

核心思想：贪心（Greedy）在每一步都选择当前看来最好的选择，并期望这样能导致全局最优解。它不是万能的，但一旦适用，代码通常极短且效率极高。

经典案例：

• 活动安排：按结束时间最早排序。

• 哈夫曼编码：合并果子问题（洛谷P1090）。

• 需要注意的是，贪心需要严格证明，否则极易出错。常见的删数问题（ZOJ1012）便是典型例子。

第4名：排序与STL运用 —— 竞赛选手的“手脚”

核心思想：排序是一切算法的基础。而在C++竞赛中，熟练运用STL（标准模板库）能让你事半功倍。

必会技能：

• sort()：自定义排序规则（cmp函数或重载运算符）。

• 容器：栈（stack）解决括号匹配、队列（queue）用于BFS、优先队列（priority_queue）用于堆优化、集合（set）用于去重与二分查找、映射（map）用于离散化处理大数据范围（如CSP第4题）。

第5名：深度优先搜索与回溯 —— 遍历一切可能

核心思想：深度优先搜索（DFS）通过递归深入每条路径，撞墙后返回。回溯是DFS的灵魂，即在递归返回时恢复状态，以便探索其他分支。

应用场景：

• 排列组合：全排列、子集生成。

• 图上路径：迷宫可行性判断。

• 树的遍历：树形DP的基础。

• 剪枝优化：如“素数环”（ZOJ1457），通过预先判断剪去不可能的分支，是搜索优化的核心。

第6名：广度优先搜索 —— 最短路的“朴素解法”

核心思想：广度优先搜索（BFS）层层推进，利用队列实现。它在无权图中第一次到达目标点的路径一定是最短的。

进阶形态：

• 双向BFS：从起点和终点同时搜索，大幅减少状态数。

• 优先队列BFS（A*的基础）：当边权不为1时，BFS退化为Dijkstra算法。

第7名：动态规划 —— 思维深度的“试金石”

核心思想：动态规划（DP）通过将复杂问题分解为简单的子问题，并利用记忆化避免重复计算。它要求问题具备最优子结构和重叠子问题。

DP学习路径：

1. 线性DP：最长上升子序列（LIS）、最长公共子序列（LCS）、最大子段和。

2. 背包问题：01背包、完全背包、多重背包。这是DP入门的必修课。

3. 区间DP：矩阵连乘、石子合并、能量项链（洛谷P1063）。

4. 树形DP：没有上司的舞会（洛谷P1352），在树上进行状态转移。

第8名：图论最短路径与最小生成树 —— 构建连接的世界

核心思想：

• 最短路径：计算两点间的最短距离。Dijkstra（单源，无负权）、Bellman-Ford/SPFA（处理负权）、Floyd（多源，全源最短路）。

• 最小生成树（MST）：用最少的边让图连通。Kruskal（加边法，并查集辅助）和Prim（加点法）。

热门考点：单源最短路径（洛谷P3371）是最基础的模板题，必须能够熟练默写堆优化版的Dijkstra。

第9名：数论基础 —— 模运算下的世界

核心思想：信息学竞赛中的数论不同于数学竞赛，更注重模运算下的规律。很多大数问题必须依靠数论转化。

必备技能：

• GCD/LCM：辗转相除法（欧几里得算法）。

• 扩展欧几里得（exgcd）：求解同余方程，求乘法逆元的基础。

• 快速幂：在O(log n)时间内计算a^b % mod。

• 素数筛法：埃氏筛、欧拉筛（线性筛），快速打出素数表。

第10名：并查集与树状数组/线段树 —— 数据结构三剑客

核心思想：

• 并查集：高效的集合合并与查询（是否在同一集合）。常用于Kruskal算法、连通块判断。

• 树状数组：单点修改、区间查询（前缀和）的利器，代码极短，但功能有局限。

• 线段树：功能极其强大，支持区间修改、区间查询（和、最大值、最小值等），是解决动态区间问题的“万能砖”。

进阶技巧：离散化配合线段树处理大数据范围；树链剖分将树上问题转化为区间问题交给线段树处理。

结语

这十大算法，就像武侠小说中的基本内功。枚举和搜索是太祖长拳，朴实刚猛；动态规划和图论是九阴真经，博大精深；数论是易筋经，洗髓伐毛。

根据清华大学出版社出版的《算法竞赛入门笔记》建议，新手不必好高骛远，应该按照“模拟/枚举 → 二分/贪心 → 搜索 → DP → 图论”的路径循序渐进。每掌握一个算法，就去在线题库（如洛谷、ZOJ、Codeforces）找对应的题目验证，将模板化为己用。

当你真正吃透这十大算法，你会在赛场上发现：所谓难题，不过是这些基础模块的组合与变形。

参考资料：
1. 赵端阳.《算法设计与分析——以ACM大学生程序设计竞赛在线题库为例（微课版）》.清华大学出版社.2025
2. 谢子扬,尹志扬.《算法竞赛入门笔记》.清华大学出版社.2025
3. 罗勇军,郭卫斌.《算法竞赛》.清华大学出版社.2019
4. 张星宇.“从大一零基础到CSP440分的认证成长实录”.中国计算机学会.2025
5. 张新华等.《信息学竞赛宝典》.人民邮电出版社.2023
*6. 李超.《48课搞定信息学奥赛：C++趣味编程》.人民邮电出版社.2025