Skip to content

02-learning-roadmap.md

Latest commit

 

History

History
373 lines (313 loc) · 11.8 KB

02-learning-roadmap.md

File metadata and controls

373 lines (313 loc) · 11.8 KB
Raw

C++ 信息学竞赛学习路线图

基于 GESP 8级 + NOI 2025 大纲的知识点分析，设计从零基础到国赛水平的完整学习路线。

学习路线总览

阶段一  →  阶段二  →  阶段三  →  阶段四  →  阶段五  →  阶段六
  │           │          │          │          │          │
C++入门    基础算法   数据结构   高级算法   CSP-S冲刺  NOI级进阶
(1-2月)    (2-3月)   (3-4月)   (3-4月)   (2-3月)   (持续)
  │           │          │          │          │          │
GESP 1-2级  GESP 3-5  GESP 5-7  GESP 7-8  GESP 8级  NOI大纲
目标:      级         级         级         CSP-S     省选+
CSP-J参赛  目标:      目标:      目标:      高分
           CSP-J一等奖 CSP-S参赛  CSP-S一等

阶段一：C++语言基础 + 简单算法（1-2个月）

对标：GESP 1-4级 | 难度：⭐⭐

第1周：C++入门

  • C++程序基本结构、编译运行环境搭建
  • 变量与常量、基本数据类型(int/long long/double/char/bool)
  • 输入输出(cin/cout/scanf/printf)
  • 运算符与表达式（算术/关系/逻辑/赋值/位运算入门）
  • 类型转换
  • 练习：50道基础输入输出题

第2周：流程控制

  • if-else / switch 分支结构
  • for / while / do-while 循环
  • 循环嵌套
  • break / continue
  • 练习：打印图形、水仙花数、素数判断等

第3周：数组与字符串

  • 一维数组（定义/初始化/遍历）
  • 二维/多维数组
  • 字符数组与C风格字符串
  • string 类型及常用操作(substr/find/erase/insert)
  • 练习：矩阵运算、字符串处理题

第4周：函数与递归基础

  • 函数定义、声明、调用
  • 参数传递（值传递/引用传递/指针传递）
  • 函数重载与默认参数
  • 递归思想（阶乘/斐波那契/汉诺塔）
  • 全局变量与局部变量、作用域
  • 练习：函数应用 + 简单递归题

第5-6周：结构体、指针与STL入门

  • 结构体(struct)定义与使用
  • 结构体数组、结构体排序
  • 指针基础(& 和 *)
  • 动态内存分配(new/delete)
  • 引用(&)与指针的区别
  • STL入门：vector / stack / queue
  • 文件操作(freopen/fstream)
  • 练习：综合性基础题 30-50道

第7-8周：基础排序与查找

  • 冒泡排序、选择排序、插入排序
  • 计数排序(桶排序)
  • 快速排序、归并排序（原理理解+手写）
  • sort() 的使用与自定义比较函数
  • 顺序查找、二分查找
  • 高精度计算（大整数加减乘除）
  • 练习：排序应用题 + 二分答案基础题

阶段二：基础算法与数据结构入门（2-3个月）

对标：GESP 5-7级 | 难度：⭐⭐⭐ | 目标：CSP-J 一等奖

第9-10周：搜索算法

  • DFS(深度优先搜索) - 全排列、组合
  • BFS(广度优先搜索) - 最短步数问题
  • 回溯算法（八皇后/数独）
  • 剪枝策略（可行性剪枝/最优性剪枝）
  • Flood Fill(连通块)
  • 练习：搜索基础题20-30道

第11-12周：贪心与分治

  • 贪心算法思想与证明思路
  • 区间调度/活动选择/最优装载
  • 分治法核心思想
  • 快速幂
  • 最大子段和(分治/DP)
  • 练习：贪心+分治题各15-20道

第13-14周：动态规划（一）

  • DP基本概念(状态/转移/边界)
  • 递推与DP的关系
  • 线性DP - 最长上升子序列(LIS)
  • 线性DP - 最长公共子序列(LCS)
  • 背包问题九讲（01背包/完全背包/多重背包）
  • 分组背包、二维费用背包
  • 练习：DP入门题30-50道

第15-16周：基础图论

  • 图的概念(顶点/边/度/连通/有向无向)
  • 图的存储（邻接矩阵/邻接表/链式前向星）
  • 图的DFS与BFS遍历
  • 欧拉路径与欧拉回路
  • 拓扑排序(Kahn算法/DFS)
  • 练习：图论基础题20-30道

第17-18周：数论基础与数学

  • 进制转换
  • 素数判定(试除法/Miller-Rabin入门)
  • 素数筛(埃氏筛/欧拉筛)
  • 最大公约数(欧几里得)/最小公倍数
  • 质因数分解
  • 排列组合基础(A/C公式)
  • 容斥原理基础
  • 杨辉三角与组合数计算
  • 练习：数学题20-30道

第19-20周：数据结构深入

  • 链表实现与应用
  • 栈的深入（括号匹配/表达式求值/单调栈）
  • 队列的深入（BFS队列/单调队列）
  • 二叉树基础（前/中/后序遍历）
  • 堆与优先队列(priority_queue)
  • 哈夫曼树
  • STL深入（set/map/unordered_map）
  • 并查集(路径压缩/按秩合并)
  • 练习：数据结构应用题各10-15道

阶段三：高级数据结构与图论（3-4个月）

对标：GESP 7-8级 | 难度：⭐⭐⭐⭐ | 目标：CSP-S 二等奖以上

第21-22周：树相关专题

  • 二叉树进阶（完全二叉树/二叉搜索树）
  • 树的直径与重心
  • 树的前缀和/差分
  • LCA（倍增法）
  • 最小生成树(Prim/Kruskal)
  • 次小生成树
  • 练习：树专题20-30道

第23-24周：最短路与连通性

  • Dijkstra算法(堆优化)
  • Bellman-Ford算法
  • SPFA优化及判断负环
  • Floyd算法
  • 差分约束系统
  • 强连通分量(Tarjan / Kosaraju)
  • 缩点技巧
  • 割点与割边(Tarjan)
  • 双连通分量
  • 练习：最短路+连通性题各15-20道

第25-26周：线段树与树状数组

  • 树状数组 BIT（单点修改/区间查询）
  • 树状数组（区间修改/单点查询，差分）
  • 二维树状数组
  • 线段树基础（建树/单点修改/区间查询）
  • 线段树懒标记（区间加/区间乘）
  • 线段树维护多种信息
  • 动态开点线段树
  • 练习：线段树/树状数组题20-30道

第27-28周：字符串算法

  • 字符串哈希(单哈希/双哈希)
  • KMP算法(前缀函数/next数组)
  • Manacher算法(最长回文子串)
  • 扩展KMP(Z函数)
  • Trie字典树
  • 01-Trie（异或极值）
  • 练习：字符串题15-20道

第29-30周：动态规划（二）

  • 区间DP（石子合并/矩阵链乘）
  • 树形DP（树上最大独立集/树的最长路径）
  • 换根DP
  • 状压DP（TSP/覆盖问题）
  • 数位DP基础
  • DP单调队列优化
  • 概率DP / 期望DP
  • 练习：DP进阶题20-30道

第31-32周：高级数据结构

  • ST表(RMQ问题)
  • 平衡树基础（set/map的红黑树理解）
  • Treap实现
  • 树链剖分(重链剖分)
  • 可持久化线段树(主席树)
  • 莫队算法（普通莫队/带修莫队）
  • 分块思想
  • 练习：高级数据结构题15-20道

阶段四：综合提高与冲刺（2-3个月）

对标：GESP 8级高分 + CSP-S 一等奖 | 难度：⭐⭐⭐⭐⭐

第33-34周：网络流与匹配

  • 最大流概念与Ford-Fulkerson方法
  • Dinic算法 + 当前弧优化
  • 最大流最小割定理
  • 二分图判定（染色法）
  • 二分图最大匹配（匈牙利算法）
  • 二分图最小点覆盖/最大独立集
  • 费用流（SPFA+EK）
  • 练习：网络流题10-15道

第35-36周：DP优化专题

  • 斜率优化DP
  • 四边形不等式优化
  • 决策单调性
  • 状态压缩DP深入
  • DP套DP思想入门
  • 练习：DP优化题10-15道

第37-38周：字符串进阶 + 杂项

  • AC自动机（多模式匹配）
  • 后缀数组(SA)入门 - 倍增法
  • 后缀数组的应用（height/lcp）
  • 中国剩余定理(CRT/exCRT)
  • 高斯消元
  • 矩阵快速幂
  • 博弈论(Nim游戏/SG函数)
  • 计算几何基础(向量/凸包/线段相交)
  • 扫描线算法
  • 练习：综合应用题15-20道

第39-40周：真题模拟与查缺补漏

  • CSP-S历年真题模拟（近5-8年）
  • GESP 8级模拟题
  • 薄弱环节专项训练
  • 考试技巧（骗分技巧/对拍/时间分配）
  • NOIP历年真题体验
  • 练习：完整模拟考试5-10套

阶段五：NOI 级进阶（持续学习）

对标：NOI 大纲 NOI级 | 难度：⭐⭐⭐⭐⭐⭐ | 目标：省选资格/NOI奖牌

此阶段在完成前四个阶段后，根据个人目标选择性学习。

模块A：网络流深化

  • 上下界网络流（无源汇/有源汇）
  • 最小割模型（最大权闭合子图/二元关系）
  • 最大权闭合子图
  • 平面图与对偶图最短路
  • 全局最小割(Stoer-Wagner)

模块B：高级数据结构

  • LCT(Link-Cut Tree)
  • 树套树（线段树套平衡树）
  • K-D Tree
  • 左偏树/配对堆
  • 块状链表
  • 虚树
  • 点分治/边分治
  • 动态DP（树剖+矩阵）
  • 李超线段树
  • 笛卡尔树

模块C：高级字符串

  • 后缀自动机(SAM)及基础应用
  • 广义后缀自动机
  • 回文自动机(PAM)
  • 后缀平衡树
  • Lyndon分解与最小表示法

模块D：高级数学

  • 莫比乌斯反演与应用
  • 杜教筛 / Min_25筛
  • 数论分块与整除分块
  • 多项式全家桶(FFT/NTT/FWT)
  • 多项式求逆/exp/ln/sqrt
  • 生成函数(OGF/EGF)系统学习
  • 群论与Burnside引理/Pólya计数
  • 线性规划/单纯形法
  • 类欧几里得算法

模块E：高级匹配

  • 一般图最大匹配(带花树算法)
  • 二分图最大权匹配(KM算法)
  • 一般图最大权匹配
  • 稳定匹配(Gale-Shapley)

模块F：高级图论

  • 支配树(Dominator Tree)
  • 2-SAT深入
  • 斯坦纳树
  • Prufer序列
  • 矩阵树定理/Kirchhoff定理
  • LGV引理
  • 树上启发式合并(dsu on tree)

模块G：计算几何

  • 凸包(Graham/Andrew)
  • 旋转卡壳
  • 半平面交
  • 平面最近点对
  • 随机增量法
  • 动态凸包
  • 三角剖分
  • 三维计算几何基础

模块H：杂项

  • CDQ分治
  • 整体二分
  • WQS二分
  • Slope Trick
  • 插头DP
  • 模拟退火与爬山算法
  • A* 与 IDA*
  • 双向搜索

推荐学习资源

在线评测系统(OJ)

OJ 网址 适合阶段
洛谷(Luogu) luogu.com.cn 全阶段，最推荐
AcWing acwing.com 阶段1-4
Codeforces codeforces.com 阶段3+
AtCoder atcoder.jp 阶段2+
UOJ uoj.ac 阶段4-5
LOJ loj.ac 阶段3-5
POJ poj.org 经典题库

教材推荐

阶段 推荐书籍
阶段1-2 《信息学奥赛一本通》
阶段1-3 《算法竞赛入门经典》(紫书)
阶段2-4 《算法竞赛进阶指南》
阶段4-5 《挑战程序设计竞赛》
阶段5 《算法导论》(CLRS) - 参考
全阶段 《OI Wiki》(oi-wiki.org)

题单建议

  • 洛谷题单：【算法1-1】模拟与高精度 → 【算法1-7】搜索
  • 洛谷题单：【数据结构1-1】线性表 → 【数据结构1-4】图的基本应用
  • 洛谷题单：【动态规划1】线性DP → 【动态规划2】背包DP
  • AcWing 算法基础课 + 算法提高课

使用建议

  1. 按顺序学习：每个阶段为后续阶段打基础，不建议跳阶段
  2. 理论+实践：每学一个知识点至少做 3-5 道练习题
  3. 做笔记：记录坑点和技巧，建立自己的"错题本"
  4. 定期复习：每周留 1 天复习前面学过的内容
  5. 参加比赛：Codeforces/AtCoder 的 rated 比赛是最好的实战检验
  6. 对拍练习：学会写暴力 + 对拍，培养调试习惯
  7. 不要死磕：一道题超过 2 小时还没思路就去查看题解，学习思路后自己实现

文档生成时间：2026-05-14 基于：GESP C++ 8级 大纲 + NOI 2025 大纲