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