信息学CSP——算法地图

面向 CSP-J / CSP-S 的信息学算法与数据结构知识库。每个算法包含直觉理解、复杂度分析、C++ 模板代码与常见坑点。

① 基础

复杂度分析
大O表示法、时间空间复杂度
CSP-J
递归
递归三要素、经典递归问题
CSP-J
分治
分而治之、归并排序
CSP-J
模拟
按题意模拟、细节处理
CSP-J
排序与离散化
常见排序、离散化技巧
CSP-J
前缀和与差分
一维/二维前缀和、差分数组
CSP-J
双指针
对撞指针、滑动窗口
CSP-J
贪心
贪心策略、证明方法
CSP-J

② 搜索

DFS 深度优先搜索
递归遍历、连通性判断
CSP-J
BFS 广度优先搜索
队列遍历、最短步数
CSP-J
记忆化搜索
缓存中间结果
CSP-S
剪枝
可行性/最优性剪枝
CSP-S
回溯
N皇后、全排列
CSP-S

③ 动态规划

背包 DP
01/完全/多重背包
CSP-S
线性 DP
LIS、LCS
CSP-S
区间 DP
石子合并、矩阵链
CSP-S
树形 DP
树的直径、最大独立集
CSP-S
状态压缩 DP
二进制状态、TSP
CSP-S
数位 DP
数位计数问题
CSP-S

④ 图论

Dijkstra 最短路
单源最短路、非负权
CSP-S
SPFA 最短路
负权边、判负环
CSP-S
Floyd 最短路
全源最短路
CSP-S
Prim 最小生成树
从点出发、稠密图
CSP-S
Kruskal 最小生成树
边排序+并查集
CSP-S
拓扑排序
DAG排序、检测环
CSP-S
Tarjan 强连通分量
DFS时间戳、缩点
CSP-S

⑤ 数据结构

栈
LIFO、单调栈
CSP-J
队列
FIFO、单调队列
CSP-J
链表
数组模拟链表
CSP-J
并查集
路径压缩、按秩合并
CSP-S
树状数组
lowbit、前缀和查询
CSP-S
线段树
区间修改、懒标记
CSP-S
ST 表
O(1)区间最值
CSP-S
堆
优先队列、Top-K
CSP-J
Trie 树
前缀树、字符串检索
CSP-S
哈希表
哈希函数、冲突处理
CSP-S

⑥ 字符串

KMP 算法
模式匹配、next数组
CSP-S

⑦ 数学

质数与筛法
素数判定、埃氏筛
CSP-J
GCD 与 LCM
辗转相除、扩展欧几里得
CSP-J
快速幂
二进制分解指数
CSP-S
逆元
费马小定理求逆元
CSP-S
组合数学
排列组合、杨辉三角
CSP-S

hsyWiki © 2026 - 信息学算法知识站  |  粤ICP备2026063027号-1