信息学算法地图
面向信息学竞赛的知识库。每个算法包含
直觉理解
、
复杂度分析
、
C++ 模板代码
与
常见坑点
。
① 基础
复杂度分析
大O表示法、时间空间复杂度
CSP-J
递归
递归三要素、经典递归问题
CSP-J
分治
分而治之、归并排序
CSP-J
模拟
按题意模拟、细节处理
CSP-J
排序与离散化
常见排序、离散化技巧
CSP-J
前缀和与差分
一维/二维前缀和、差分数组
CSP-J
双指针
对撞指针、滑动窗口
CSP-J
贪心
贪心策略、证明方法
CSP-J
二分查找与二分答案
有序查找、最优解判定
CSP-J
高精度计算
大整数四则运算
CSP-J
倍增法
ST表、LCA预处理
CSP-S
② 搜索
DFS 深度优先搜索
递归遍历、连通性判断
CSP-S
BFS 广度优先搜索
队列遍历、最短步数
CSP-S
记忆化搜索
缓存中间结果
CSP-S
剪枝
可行性/最优性剪枝
CSP-S
回溯
N皇后、全排列
CSP-S
迭代加深搜索
深度限制、逐步扩展
CSP-S
双向 BFS
从两端同时搜索
CSP-S
③ 动态规划
背包 DP
01/完全/多重背包
CSP-S
线性 DP
LIS、LCS
CSP-S
区间 DP
石子合并、矩阵链
NOIP
树形 DP
树的直径、最大独立集
CSP-S
状态压缩 DP
二进制状态、TSP
NOIP
数位 DP
数位计数问题
NOIP
最长上升子序列
O(nlogn) 贪心+二分
CSP-S
最长公共子序列
二维DP、子串匹配
CSP-S
单调队列优化 DP
滑动窗口最值优化
NOIP
斜率优化 DP
凸包优化、直线转移
NOIP
④ 图论
Dijkstra 最短路
单源最短路、非负权
CSP-S
SPFA 最短路
负权边、判负环
CSP-S
Floyd 最短路
全源最短路
CSP-S
Prim 最小生成树
从点出发、稠密图
CSP-S
Kruskal 最小生成树
边排序+并查集
CSP-S
拓扑排序
DAG排序、检测环
CSP-S
Tarjan 强连通分量
DFS时间戳、缩点
NOIP
最近公共祖先
倍增/Tarjan求LCA
NOIP
树上差分
路径统计、节点覆盖
NOIP
匈牙利算法
二分图最大匹配
NOIP
欧拉路径与回路
Hierholzer 算法
NOIP
网络流（Dinic）
最大流、残量网络
NOI
2-SAT
布尔方程组、SCC
NOI
⑤ 数据结构
栈
LIFO、单调栈
CSP-J
队列
FIFO、单调队列
CSP-J
链表
数组模拟链表
CSP-J
并查集
路径压缩、按秩合并
CSP-S
树状数组
lowbit、前缀和查询
NOIP
线段树
区间修改、懒标记
NOIP
ST 表
O(1)区间最值
NOIP
堆
优先队列、Top-K
CSP-J
Trie 树
前缀树、字符串检索
CSP-S
哈希表
哈希函数、冲突处理
CSP-S
单调栈
下一个更大/更小元素
CSP-S
单调队列
滑动窗口最值
CSP-S
可持久化线段树
主席树、历史版本
NOI
⑥ 字符串
KMP 算法
模式匹配、next数组
CSP-S
字符串哈希
滚动哈希、子串比较
CSP-S
Manacher
最长回文子串 O(n)
NOIP
AC 自动机
多模式串匹配
NOI
后缀数组
SA、LCP、后缀排序
NOI
⑦ 数学
质数与筛法
素数判定、埃氏筛
CSP-J
GCD 与 LCM
辗转相除、扩展欧几里得
CSP-J
快速幂
二进制分解指数
CSP-S
逆元
费马小定理求逆元
CSP-S
组合数学
排列组合、杨辉三角
CSP-S
扩展欧几里得
逆元、线性同余方程
CSP-S
博弈论
Nim、SG函数
NOIP
Lucas 定理
大组合数模质数
NOIP
矩阵快速幂
递推加速、斐波那契
NOIP
高斯消元
线性方程组、异或方程
NOIP
容斥原理
计数、概率、反演
NOIP
中国剩余定理
同余方程组合并
NOIP
Catalan 数
括号序列、路径计数
CSP-S
快速傅里叶变换
多项式乘法、卷积
NOI
计算几何：凸包
Andrew算法、叉积
NOI
线性基
异或空间、最大异或和
NOI
