在信息学奥赛（NOI系列赛事、CSP-J/S）的备赛过程中，无数选手常常面对这样一个困境：算法书越读越厚，知识点越学越散，刷题时却总觉得无从下手。动态规划（DP）的“七十二变”、图论算法的“眼花缭乱”、数论知识的“高深莫测”，常常让初学者望而却步，也让进阶者难以构建完整的知识体系。
其实，信息学奥赛的知识点并非孤立的海岛，而是一片紧密相连的大陆。本文将为你梳理一张关于DP、图论、数论的算法思维导图，将这三个核心板块“一网打尽”，帮助你建立系统化的知识框架，理清学习路径，从“只见树木”到“只见森林”。
一、动态规划：从朴素到优化的思维跃迁
动态规划是信息学奥赛中考察频率最高、思维难度也最大的板块之一。它的核心思想是“记住过去，推导未来”，即通过将复杂问题分解为简单的子问题，并利用子问题的解来构建原问题的解 。
1. 基础DP：模型的构建
线性DP 是最基础的入门模型，其状态转移具有明显的方向性。典型问题包括最长上升子序列（LIS）、最长公共子序列（LCS）等。这类问题帮助选手理解“状态”与“决策”的概念 。背包DP 则是另一类经典问题，包括0/1背包、完全背包、多重背包和分组背包。背包问题不仅是DP的入门必修课，更是理解“空间复杂度优化”（如滚动数组）的最佳实践场 。
2. 进阶DP：维度的拓展
当问题不再局限于线性序列，就进入了区间DP和树形DP的领域。区间DP（如石子合并、矩阵链乘）通常以“区间长度”作为阶段，枚举分割点进行状态转移。树形DP则是在树上进行动态规划，经典的“没有上司的舞会”问题展示了如何在树的节点上定义状态（选或不选），并通过深度优先搜索进行转移 。
状态压缩DP 是应对NP问题中“小数据范围”的利器。当状态维度极高（如一个集合的选择情况），但数据范围较小（n≤20）时，可以用二进制位来表示状态，将复杂的状态压缩成一个整数 。而数位DP则专门解决“在某个区间内满足某种数字性质（如不含62）的数有多少个”这类问题，通过逐位处理，将复杂的枚举转化为可控的状态转移 。
3. 优化DP：性能的飞跃
随着问题难度的提升，基础DP往往会面临“超时”的窘境。这时就需要引入优化策略。单调队列优化和斜率优化常用于解决形如 dp[i] = max(dp[j] + cost(j,i)) 且具有单调性的转移方程 。四边形不等式优化则适用于特定类型的区间DP，能够将复杂度从O(n³)降至O(n²)。对于具有“阶段性”的线性递推问题，矩阵快速幂优化则能将复杂度从O(n)降至O(log n) 。
二、图论：连接万物的数据结构
图论算法是信息学奥赛中代码量最大、综合性最强的板块。它研究的是顶点与边构成的各种关系 。
1. 图的遍历与连通性
图的构建是一切操作的基础。选手必须熟练掌握邻接矩阵、邻接表以及效率极高的链式前向星 。在此基础上，拓扑排序 是处理有向无环图（DAG）的利器，常用于检测图中是否存在环以及进行任务调度 。
连通性问题 是图论的一个核心分支。并查集 以其简洁的代码和高效的处理能力，在判断无向图的连通分量和Kruskal算法中大放异彩 。对于有向图的强连通分量，Tarjan算法 是必备技能，它能通过缩点将复杂的有环图转化为有向无环图，从而简化问题 。此外，求无向图的割点与桥（割边） 以及最近公共祖先（LCA），都是NOIP及以上难度的高频考点 。
2. 最短路径与生成树
最短路径 算法构成了一个完整的体系：Floyd-Warshall 算法（弗洛伊德算法）适合求解多源最短路，也能用于传递闭包；Dijkstra 算法（迪杰斯特拉算法）是求解单源最短路的首选，其堆优化版本是竞赛中的标准写法；Bellman-Ford 算法及其队列优化版本SPFA 则适用于存在负权边的图 。
最小生成树 问题常用Kruskal（克鲁斯卡尔算法，基于并查集+排序）或Prim（普里姆算法，类似于Dijkstra）算法解决 。对于更复杂的问题，如次小生成树、差分约束系统（将不等式问题转化为最短路问题）以及欧拉路径（一笔画问题），则需要更深的理解和灵活的应用 。
3. 网络流与高级模型
作为图论的天花板，网络流 主要出现在NOI级别的比赛中。最大流（Dinic算法、ISAP算法）和最小割是解决资源调度、冲突划分问题的万能钥匙。最小费用最大流则在实际问题中应用更广 。掌握网络流的关键不仅在于背诵模板，更在于如何识别问题背后的“流量”模型，即“建图”。
三、数论：算法竞赛中的数学基石
如果说图论是算法竞赛的骨架，那么数学就是算法的灵魂。数论作为数学分支中与竞赛结合最紧密的一环，主要研究整数的性质 。
1. 基础数论：从入门到进阶
一切数论的基础都源于整除、质数、最大公约数（GCD） 和最小公倍数（LCM）。欧几里得算法（辗转相除法）是求GCD的最经典方法，而扩展欧几里得算法（Exgcd）则进一步用于求解形如 ax + by = gcd(a, b) 的不定方程，是解决模线性方程的基础 。
质数筛查 是竞赛中的基本功，从简单的埃拉托斯特尼筛法（埃氏筛）到线性的欧拉筛，选手必须熟练掌握其原理及代码实现 。快速幂 则利用二分思想，在O(log n)时间内求出 a^b mod p，是处理大数幂取模的必备工具 。
2. 同余与数论函数
同余 理论是数论的核心。费马小定理 和欧拉定理为模运算下的指数取模提供了简化依据。乘法逆元 的求解（通常通过快速幂或Exgcd）则是处理模意义下除法运算的关键 。中国剩余定理（CRT） 专门用于求解一元线性同余方程组 。
对于更高阶的选手，莫比乌斯反演 和欧拉函数 的应用成为拉分的关键。这些内容常与积性函数结合，利用线性筛进行求解，解决诸如互质对数、公约数之和等复杂的计数问题 。
3. 组合数学与线性代数
除了纯数论，排列组合、容斥原理、卡特兰数、斯特林数 等组合数学知识也是信息学奥赛的重要组成部分 。它们常与DP、概率期望等结合，考察选手的建模能力。高斯消元法 用于求解线性方程组，是解决某些期望DP问题的最后一步 。而快速傅里叶变换（FFT） 则能在O(n log n)时间内计算多项式乘法，在处理大数乘法或特定卷积问题时有着不可替代的作用 。
四、构建你自己的思维导图
学习算法，切忌死记硬背。建议你根据以上梳理，亲手绘制一张属于自己的思维导图：
- 主干三大支：画出DP、图论、数论三个主分支。
- 二级分支定难度：按照入门（CSP-J）、核心（CSP-S）、进阶（NOIP）、高难（NOI）为各个知识点标注难度等级 。
- 三级分支连细节：记录每个核心算法的模板代码位置、经典例题以及易错点。
- 交叉连接建体系：用虚线连接不同分支的交叉点，如“矩阵快速幂优化DP”、“高斯消元求解期望DP”、“状压DP解决图论旅行商问题”。这种交叉融合往往是难题的命题方向。
| 核心板块 | 学习阶段 | 重点内容 | 常见题型/应用 |
|---|---|---|---|
| 动态规划 (DP) | 入门 | 线性DP、背包DP | 最长上升子序列、0/1背包 |
| 进阶 | 区间DP、树形DP、状压DP | 石子合并、没有上司的舞会 | |
| 优化 | 斜率优化、矩阵快速幂优化 | 转移方程具有单调性的复杂DP | |
| 图论 | 基础 | 邻接表、拓扑排序、并查集 | 图的存储与遍历、判环、连通分量 |
| 核心 | 最短路径、最小生成树、LCA | Dijkstra、Kruskal、树上最近公共祖先 | |
| 高级 | 网络流、Tarjan、差分约束 | 最大流、缩点、不等式关系转化 | |
| 数论与数学 | 基础 | 欧几里得算法、埃氏筛、快速幂 | GCD/LCM、质数判断、大数幂取模 |
| 核心 | 扩展欧几里得、乘法逆元、CRT | 解不定方程、模意义下除法、同余方程组 | |
| 高阶 | 莫比乌斯反演、FFT、高斯消元 | 复杂计数问题、多项式乘法、求解线性方程组/期望DP |
信息学奥赛的学习之路，本质上是一场与智力的马拉松。当你将DP的“状态”、图论的“关系”、数论的“规律”一一纳入自己的知识网络，你会发现，所谓的难题不过是几个基础模型的巧妙组合。希望这张思维导图能成为你攀登路上的“地图”，助你在算法的海洋中，乘风破浪，直济沧海。