信息学奥林匹克竞赛知识点图谱（颜色修正版）
1. 编程基础与入门算法 (CSP-J)
| 基础语法 | 数据结构入门 | 基础算法 |
|---|---|---|
| 分支结构 [蓝] | 数组/数组下标 [蓝] | 冒泡/选择/插入排序 [蓝] |
| 循环结构 [蓝] | 字符/字符串操作 [蓝] | Sort排序 [蓝] |
| 结构体/自定义排序 [蓝] | 栈/单调栈(符号匹配) [蓝] | 递归/DFS排列组合/方案数 [蓝] |
| Map/Vector [蓝] | 单向/双向链表 [蓝] | BFS最短路 [蓝] |
| 一维/二维前缀和 [蓝] | 队列/双向队列/单调队列 [蓝] | 二分查找 [蓝] |
| 一维/二维差分 [蓝] | 二分答案 [蓝] |
2. 算法核心 (CSP-S / NOIP)
| 动态规划 (DP) | 图论 | 搜索 | 数学基础 |
|---|---|---|---|
| CSP-S (黄色) | 记忆化搜索 [黄] | 筛法(埃氏筛/欧拉筛) [黄] | |
| 线性DP [黄] | 邻接表/邻接矩阵 [黄] | 迭代加深搜索 [黄] | 分解质因数 [黄] |
| 背包DP [黄] | 链式前向星 [黄] | 双向BFS/折半搜索 [黄] | GCD/LCM [黄] |
| 区间DP [黄] | 拓扑排序 [黄] | 快速幂 [黄] | |
| DAG上DP [黄] | 最小生成树(Prim/Kruskal) [黄] | 排列组合 [黄] | |
| 树形DP [黄] | 最短路(Dijkstra, Floyd, SPFA) [黄] | 费马小定理 [黄] | |
| 树的直径/重心 [黄] | 二分图判定 [黄] | 乘法逆元(基础) [黄] | |
| 位运算技巧 [黄] | |||
| 离散化 [黄] | |||
| NOIP (绿色) | NOIP (绿色) | ||
| 树形背包 [绿] | 强连通分量(Tarjan) [绿] | 容斥原理 [绿] | |
| 换根DP [绿] | 割点/割边(桥) [绿] | 矩阵快速幂 [绿] | |
| 状压DP [绿] | LCA [绿] | 高斯消元法 [绿] | |
| 数位DP [绿] | 树上差分 [绿] | ||
| 期望/概率DP [绿] | 欧拉路径/回路 [绿] | ||
3. 高级数据结构 (CSP-S / NOIP / NOI)
| CSP-S (黄色) | NOIP (绿色) | NOI (红色) |
|---|---|---|
| 堆/优先队列 [黄] | 线段树(基本操作) [绿] | 可持久化线段树 [红] |
| 对顶堆 [黄] | 线段树合并/分裂 [红] | |
| 并查集(基础) [黄] | 平衡树(概念) [红] | |
| ST表 [黄] | 二维线段树 [红] | |
| 字典树Trie [黄] | 吉如一线段树 [红] | |
| 树状数组 [黄] | 扫描线 [红] |
4. 进阶与专项 (NOI)
| 动态规划优化 | 图论进阶 | 字符串高级 | 数学进阶 |
|---|---|---|---|
| 矩阵加速DP [红] | 网络流(最大流/最小割) [红] | AC自动机 [红] | 扩展欧几里得 [红] |
| 斜率优化DP [红] | 点/边双连通分量 [红] | 后缀自动机(SAM) [红] | 中国剩余定理 [红] |
| 四边形不等式优化DP [红] | 树链剖分 [红] | 扩展KMP [红] | 莫比乌斯反演 [红] |
| 动态DP [红] | 基环树 [红] | 线性基 [红] | |
| 点分治/边分治 [红] | 快速傅里叶变换(FFT) [红] | ||
| 差分约束系统 [红] | 计算几何(凸包) [红] | ||
| K短路 [红] | 斯特林数 [红] | ||
| 启发式搜索 A* [红] | 01分数规划 [红] | ||
| 模拟退火 [红] |
颜色含义：蓝色(CSP-J)代表必须掌握，黄色(CSP-S)代表核心考点，绿色(NOIP)代表进阶内容，红色(NOI)代表高难专项。
0 条评论
目前还没有评论...
