OI学习笔记 - 学习路径

发表于 2025-04-01 更新于 2025-04-03 阅读次数：本文字数： 1.7k 阅读时长 ≈ 3 分钟

一、基础

基础

容器
- vector
- list
- deque
- set
- map
- stack
- queue
算法
- sort
- binary_search
- next_permutation
其他
- pair
- tuple
- 命名空间
- λ表达式
- pb_ds

算法复杂度分析

时间复杂度
空间复杂度

二、核心算法

算法基础

枚举
- 一维枚举
  - 应用场景：遍历数组或列表
  - 优化技巧：剪枝、减少冗余
- 二维枚举
  - 应用场景：矩阵或二维数组
  - 优化技巧：循环嵌套优化
- 多维枚举
  - 应用场景：高维数据
  - 优化技巧：降维处理
模拟
- 直接模拟
  - 应用场景：按步骤模拟问题过程
  - 优化技巧：减少不必要的计算
- 状态模拟
  - 应用场景：状态变化问题
  - 优化技巧：状态压缩
- 事件驱动模拟
  - 应用场景：事件触发的动态过程
  - 优化技巧：事件优先处理
递归 & 分治
- 递归
  - 基本概念：函数调用自身
  - 应用场景：树结构、回溯问题
  - 优化技巧：记忆化递归、尾递归
- 分治
  - 基本概念：分而治之
  - 应用场景：排序、大规模数据处理
  - 优化技巧：平衡子问题规模
贪心
- 基本概念：局部最优选择
- 应用场景：最优化问题
- 优化技巧：贪心选择性质、验证贪心策略
- 典型问题：活动选择、背包问题、霍夫曼编码
排序
- 冒泡排序
  - 时间复杂度：O(n²)
  - 应用场景：小规模数据
- 选择排序
  - 时间复杂度：O(n²)
  - 应用场景：小规模数据
- 插入排序
  - 时间复杂度：O(n²)
  - 应用场景：部分有序数据
- 快速排序
  - 时间复杂度：O(n log n)
  - 应用场景：大规模数据
- 归并排序
  - 时间复杂度：O(n log n)
  - 应用场景：稳定性要求高
- 堆排序
  - 时间复杂度：O(n log n)
  - 应用场景：内存限制场景
- 计数排序
  - 时间复杂度：O(n + k)
  - 应用场景：整数排序
- 桶排序
  - 时间复杂度：O(n + k)
  - 应用场景：数据分布均匀
- 基数排序
  - 时间复杂度：O(nk)
  - 应用场景：多位数字排序
前缀和 & 差分
- 前缀和
  - 一维前缀和
    - 应用场景：区间求和
  - 二维前缀和
    - 应用场景：矩阵区间求和
- 差分
  - 一维差分
    - 应用场景：区间更新
  - 二维差分
    - 应用场景：矩阵区间更新
二分
- 二分查找
  - 基本概念：有序数组查找
  - 应用场景：查找目标值或边界
  - 变种：左边界、右边界、第一个大于等于
- 二分答案
  - 基本概念：通过二分猜测答案
  - 应用场景：最优化问题
  - 优化技巧：验证函数设计
倍增
- 基本概念：利用指数增长加速计算
- 应用场景：快速幂、LCA问题
- 优化技巧：预处理倍增表
构造
- 基本概念：设计特定结构解决问题
- 应用场景：特定问题的解决方案设计
- 优化技巧：构造规则验证
- 典型问题：拉丁方阵、魔方阵、图的构造

搜索算法

广度优先搜索（BFS）
- 队列实现
- 应用场景
深度优先搜索（DFS）
- 栈实现
- 应用场景
回溯法
- 剪枝
- 应用场景
**A*算法**
- 启发式搜索
- 应用场景

贪心算法

基本概念
- 局部最优
- 全局最优
经典问题
- 活动选择问题
- 背包问题
- 最小生成树
- 最短路径

分治算法

基本概念
- 分解
- 解决
- 合并
经典问题
- 快速排序
- 归并排序
- 大数相乘
- 最近点对问题

动态规划

基本概念
- 阶段
- 状态
- 决策
- 状态转移方程
- 最优子结构
- 重叠子问题
经典问题
- 背包问题
  - 01背包
  - 完全背包
  - 多重背包
- 最长公共子序列
- 最长递增子序列
- 编辑距离
- 矩阵链乘
- 图像压缩
- 生产调度
- 股票买卖
- 石头游戏

回溯法

排列组合
- 全排列
- 组合
- 子集
- 分割问题
棋盘问题
- N皇后
- 解数独
其他问题
- 括号生成
- 旅行商问题（TSP）

三、数据结构

基础数据结构

数组
- 一维数组
- 二维数组
- 多维数组
链表
- 单链表
- 双链表
- 循环链表
栈
- 顺序栈
- 链式栈
队列
- 顺序队列
- 链式队列
- 循环队列
- 双端队列
集合
映射

树

二叉树
- 二叉树的遍历
  - 前序遍历
  - 中序遍历
  - 后序遍历
  - 层序遍历
- 二叉搜索树
- 平衡二叉树
  - AVL树
  - Treap树
  - 红黑树
- 堆
  - 大顶堆
  - 小顶堆
其他树
- Trie树
- 线段树
- 树状数组
- 并查集

图

图的存储
- 邻接矩阵
- 邻接表
图的遍历
- 深度优先搜索
- 广度优先搜索
最短路径
- Dijkstra算法
- Bellman-Ford算法
- SPFA算法
- Floyd-Warshall算法
最小生成树
- Prim算法
- Kruskal算法
其他
- 拓扑排序
- 强连通分量
- 二分图匹配
- 最大流
- 最小割

四、数学理论基础

数论

素数
- 素数判定
- 素数筛选
约数
- 最大公约数
- 最小公倍数
同余
- 模运算
- 中国剩余定理
欧拉定理
费马小定理
快速幂
矩阵快速幂
扩展欧几里得算法
逆元

组合数学

排列组合
- 加法原理
- 乘法原理
- 排列
- 组合
容斥原理
鸽巢原理
递推关系
母函数
生成函数
斯特林数
卡特兰数

概率论

随机事件与概率
条件概率
贝叶斯定理
随机变量
概率分布
期望与方差
协方差与相关系数
大数定律与中心极限定理

几何

平面几何
- 点与向量
- 点积与叉积
- 直线与线段
- 多边形
- 凸包
- 最近点对
- 旋转卡壳
- 半平面交
三维几何
- 点与向量
- 直线与平面
- 多面体
- 凸包
- 最小圆覆盖