基础算法与数学总结目录

haozexu · 2023-07-21 08:06:51 · 闲话

基础算法与数学总结目录

1. 综述

基础算法是解决问题的基本方法（二分、排序、位运算、前缀和、离散化、ST等）与思想（分治、倍增、贪心、二进制划分等）。

这些算法与思想是构建更高级算法与数据结构的基础，这些高级的东西是通过对于问题的划分、归纳、提取、抽象这些等等来优化遍历状态空间的效率。

数学章节主要讲述常用于程序设计中的数学知识。这些数学知识帮助优化程序的时空效率、编程复杂度等等。

本节的重点有以下几种，其余可能略写：

• 0x00基础算法

  • 二分

  • 倍增（ST算法）

  • 贪心

• 0x10基本数据结构

  • 单调栈/单调队列

  • Hash

  • KMP字符串匹配

  • Tire

  • 二叉堆/Huffman Tree

• 0x20搜索

  • 搜索剪枝（记忆化等）/搜索优化（双向搜索等）

  • 广搜变形（双端队列BFS等）

  • Astar/IDAstar

• 0x30数学

  • 质数筛法

  • 最大公约数

  • 欧拉函数

  • 同余

  • 欧拉定理与费马小定理

  • 扩展欧几里得算法与乘法逆元

  • 求解线性同余方程/方程组

  • 矩阵乘法

  • 高斯消元

  • 组合数学

  • 容斥原理

  • 概率与数学期望

  • 0/1分数规划

  • 博弈论与SG函数

数学单元太大了qwq

注：以上列出的为详述主题，标粗的为重点主题（会单独开标题），未列出的为略讲主题。一些比较相近的单元已被合并。

这期 \LaTeX 均使用比较舒适的写法。