OI省选知识点

字数统计: 538字   |   阅读时长: 1min

数据结构

  1. 带权并查集
  2. 线段树合并
  3. 平衡树
    • Treap 随机平衡二叉树
    • FHQ Treap
  4. 分块
  5. 树套树
    • 线段树套平衡树
    • 平衡树套线段树
  6. 可并堆
    • 左偏树
  7. KDtree,四分树
  8. 可持久化数据结构(主席树等)

字符串相关算法及数据结构

  1. KMP
  2. AC自动机
  3. 后缀数组
  4. 后缀自动机
  5. 字典树 Trie
  6. manacher

图论相关

  1. 最小生成树
    • prim
    • kruskal
  2. 最短路，次短路，K短路
    • spfa
    • dijkstra
    • floyd
  3. 图的连通
    • 连通分量
    • 割点，割边
  4. 网络流
    • 最大流
    • 最小割
    • 费用流
    • 分数规划
  5. 树相关
    • 树上倍增，公共祖先
    • 树链剖分
    • 树的分治算法（点分治，边分治，树分治）
    • 动态树 （LCT，树分块）
    • 虚树
  6. 拓扑排序
  7. 欧拉图
  8. 二分图

数学相关

  1. （扩展）欧几里得算法，筛法，快速幂
    • 斐蜀定理
    • 更相减损术
  2. 欧拉函数与*降幂大法
  3. 费马小定理
  4. 排列组合
    • lucas定理
  5. 乘法逆元
  6. 矩阵乘法
  7. 数学期望与概率
  8. 博弈论
    • sg函数
    • 树上删边游戏
  9. 拉格朗日乘子法
  10. 中国剩余定理
  11. 线性规划与网络流
  12. 单纯型线性规划
  13. 辛普森积分
  14. 模线性方程组
  15. 容斥原理与莫比乌斯反演
  16. 置换群
  17. 快速傅里叶变换

动态规划

  1. 一般，背包，状压，区间，环形，树形，数位动态规划
    • 记忆化搜索
    • 斯坦纳树
    • 背包九讲
  2. 斜率优化与四边形不等式优化
  3. 环 + 外向树上的动态规划
  4. 插头动态规划

计算几何

  1. 计算几何基础
  2. 三维计算几何初步
  3. 梯形剖分与三角形剖分
  4. 旋转卡壳
  5. 半平面交
  6. pick定理
  7. 扫描线

搜索相关

  1. bfs，dfs
  2. A* 算法
  3. 迭代加深搜索，双向广搜

特殊算法

  1. 莫队算法，*树上莫队
  2. 模拟退火
  3. 爬山算法
  4. 随机增量法

其它重要工具与方法

  1. 模拟与贪心
  2. 二分，三分法（求偏导）
  3. 分治，CDQ分治
  4. 高精度
  5. 离线
  6. ST表

STL

  1. map
  2. priority_queue
  3. set
  4. bitset
  5. rope

非常见算法

  1. *朱刘算法
  2. *弦图与区间图
本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/56008cdb.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

    			  jsonContent:
				meta: false
				pages: false
				posts:
				  title: true
				  date: true
				  path: true
				  text: false
				  raw: false
				  content: false
				  slug: false
				  updated: false
				  comments: false
				  link: false
				  permalink: false
				  excerpt: false
				  categories: false
				  tags: true


There's nothing