codeforces-go 💭💡🎈

算法 Algorithm

由于算法知识点多且杂，将自己学习到的算法、做过的题目分类整理好是有必要的。

一个算法模板应当涵盖下面几点：

对该算法的基本介绍（核心思想、复杂度等）
参考链接或书籍章节（讲的比较好的资料）
模板代码（可以包含一些注释、使用说明）
模板补充内容（常见题型中的额外代码、建模技巧等）
相关题目链接（模板题、经典题、思维转换题等）

算法目录

数据结构
- 双端队列 deque.go
- 堆（优先队列）heap.go
- 单调栈 monotone_stack.go
- 单调队列 monotone_queue.go
- 并查集 union_find.go
  - 点权
  - 边权（种类）
  - 动态图连通性
- 稀疏表（ST 表）sparse_table.go
- 树状数组 fenwick_tree.go
- 线段树 segment_tree.go
  - 懒标记
  - 持久化（主席树）
- 左偏树（可并堆）leftist_tree.go
- 笛卡尔树 cartesian_tree.go
- 二叉搜索树公共方法 bst.go
- Treap treap.go
- 伸展树 splay.go
- 动态树 LCT link_cut_tree.go
- 红黑树 red_black_tree.go
- 替罪羊树 scapegoat_tree.go
- k-d 树 kd_tree.go
- 珂朵莉树（ODT）
  - 数组版 odt.go
  - 平衡树版 odt_bst.go
- 根号算法（分块）sqrt_decomposition.go
- 莫队算法 mo.go
  - 带修莫队
  - 回滚莫队
  - 树上莫队
字符串 strings.go
- Hash
- KMP
- 扩展 KMP（Z algorithm）
- 最小表示法
- Manacher
- 后缀数组（SA）
- 字典树 trie.go
  - AC 自动机
- 异或字典树 trie01.go
  - Hack：构造一组数据，最大化树上的节点数
数学
- 数论 math.go
  - 最大公因数（GCD）
  - 类欧几里得算法 ∑⌊(ai+b)/m⌋
  - Pollard-Rho
  - 线性筛
  - 欧拉函数
  - 原根
  - 扩展 GCD
  - 逆元
  - 中国剩余定理（CRT）
  - 扩展中国剩余定理（EXCRT）
  - 离散对数
    - 小步大步算法（BSGS）
    - 扩展小步大步算法（exBSGS）
    - 二次剩余
    - Jacobi 符号
  - 莫比乌斯函数
  - 数论分块
  - 杜教筛
  - 拉格朗日插值
- 快速傅里叶变换 FFT math_fft.go
- 快速数论变换 NTT math_ntt.go
  - 包含多项式全家桶（求逆、开方等等）
- 连分数、佩尔方程 math_continued_fraction.go
- 线性代数 math_matrix.go
  - 矩阵相关运算
  - 高斯消元
  - 行列式
  - 线性基
- 计算几何 geometry.go
  - 直线和点
  - 直线和直线
  - 直线和圆
  - 圆和圆
  - 凸包
  - 最近点对
  - 最远点对
- 博弈论 games.go
  - SG 函数
动态规划 dp.go
- 背包
- 线性 DP
- 区间 DP
- 状压 DP
- 数位 DP
- 树形 DP
  - 换根 DP
图论 graph.go
- 欧拉回路
- 割点
- 割边（桥）
- 双连通分量
- 最短路
  - Dijkstra
  - SPFA
  - Floyd-Warshall
  - Johnson
  - 0-1 BFS
- 最小生成树
  - Kruskal
  - Prim
- 最小差值生成树
- 最小树形图
  - 朱刘算法
- 二分图最大匹配
- 带权二分图最大完美匹配
- 拓扑排序
- 强连通分量
  - Kosaraju
  - Tarjan
- 2-SAT
- 基环树
- 最大流
  - Dinic
  - ISAP
  - HLPP
- 最小费用最大流
  - SPFA
  - Dijkstra
- 树上问题 graph_tree.go
  - 直径
  - 重心
    - 点分治
  - 最近公共祖先（LCA）
    - 倍增
    - ST 表
    - Tarjan
    - 树上差分
  - 树链剖分（重链剖分，HLD）
  - 长链剖分
  - 树上启发式合并（DSU）
  - 树分块
其他
- 位运算笔记 bits.go
  - bitset
- 三分查找 sort.go
- 0-1 分数规划 sort.go
- 随机算法 rand.go
  - 模拟退火
快读模板 io.go

如何选择题目 How to Choose Problems

我的方法很简单，选择难度在自己 rating 到 rating+200 范围内的构造题 (tag: constructive algorithms) 或数学题 (tag: math)，按照过题人数降序，比如 [2100,2300] 区间的就是下面这个链接：

https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=combine-tags-by-or%2Cconstructive+algorithms%2Cmath%2C2100-2300

为什么要选构造和数学？做构造能提高观察能力，快速找到切题入口；做数学能提高挖掘题目本质的能力。做这两类题目对提高问题的分析能力大有裨益。

我的 Codeforces 账号：

测试及对拍 Testing

编写一个 run(io.Reader, io.Writer) 函数来处理输入输出。这样写的理由是：

在 main 中调用 run(os.Stdin, os.Stdout) 来执行代码；
测试时，将测试数据转换成 strings.Reader 当作输入，并用一个 strings.Builder 来接收输出，将这二者传入 run 中，然后就能比较输出与答案了；
对拍时需要实现一个暴力算法 runAC，参数和 run 一样。通过随机数据生成器来生成数据，分别传入 runAC 和 run，通过比对各自的输出，来检查 run 中的问题。