README
¶
codeforces-go 💭💡🎈
算法 Algorithm
由于算法知识点繁杂，将自己学习到的算法、做过的题目分类整理好是有必要的。
一个算法模板应当涵盖以下几点：
- 对该算法的基本介绍（核心思想、复杂度等）
- 参考链接或书籍章节（讲的比较好的资料）
- 模板代码（可以包含一些注释、使用说明）
- 模板补充内容（常见题型中的额外代码、建模技巧等）
- 相关题目链接（模板题、经典题、思维转换题等）
算法目录
- 数据结构
- 单调栈 monotone_stack.go
- 单调队列 monotone_queue.go
- 双端队列 deque.go
- 堆（优先队列）heap.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）
- 根号算法（分块）sqrt_decomposition.go
- 莫队算法 mo.go
- 普通莫队
- 带修莫队
- 回滚莫队
- 树上莫队
- 字符串 strings.go
- 字符串哈希
- KMP
- 最小循环节
- 扩展 KMP（Z algorithm）
- 最小表示法
- 最长回文子串
- Manacher 算法
- 后缀数组（SA）
- 字典树 trie.go
- 持久化
- AC 自动机
- 异或字典树 trie01.go
- 持久化
- Hack：构造一组数据，最大化树上的节点数
- 数学
- 数论 math.go
- 最大公因数（GCD）
- 类欧几里得算法 ∑⌊(ai+b)/m⌋
- Pollard-Rho 质因数分解算法
- 埃氏筛
- 线性筛
- 欧拉函数
- 原根
- 扩展 GCD
- 二元一次不定方程
- 逆元
- 线性求逆元
- 中国剩余定理（CRT）
- 扩展中国剩余定理
- 离散对数
- 大步小步算法（BSGS）
- 扩展大步小步算法
- 二次剩余
- Jacobi 符号
- 大步小步算法（BSGS）
- 组合数学
- 卢卡斯定理
- 卡特兰数
- 默慈金数
- 那罗延数
- 斯特林数
- 第一类斯特林数（轮换）
- 第二类斯特林数（子集）
- 贝尔数
- 莫比乌斯函数
- 数论分块
- 杜教筛
- 容斥原理
- 快速傅里叶变换 FFT math_fft.go
- 快速数论变换 NTT math_ntt.go
- 包含多项式全家桶（求逆、开方等等）
- 快速沃尔什变换 FWT math_fwt.go
- 连分数、佩尔方程 math_continued_fraction.go
- 线性代数 math_matrix.go
- 矩阵相关运算
- 高斯消元
- 行列式
- 线性基
- 数值分析 math_numerical_analysis.go
- 自适应辛普森积分
- 拉格朗日插值
- 计算几何 geometry.go
- 线与点
- 线与线
- 圆与点
- 最小圆覆盖
- 随机增量法
- 固定半径覆盖最多点
- 最小圆覆盖
- 圆与线
- 圆与圆
- 圆与矩形
- 最近点对
- 多边形与点
- 凸包
- 最远点对
- 旋转卡壳
- 半平面交
- 博弈论 games.go
- SG 函数
- 数论 math.go
- 动态规划 dp.go
- 背包
- 0-1 背包
- 完全背包
- 多重背包
- 分组背包
- 树上背包（依赖背包）
- 字典序最小方案
- 线性 DP
- 最大子段和
- LCS
- LPS
- LIS
- 狄尔沃斯定理
- LCIS
- 长度为 m 的 LIS 个数
- 本质不同子序列个数
- 区间 DP
- 环形 DP
- 状压 DP
- 旅行商问题（TSP）
- 高维前缀和（SOS DP）
- 插头 DP
- 数位 DP
- 倍增优化 DP
- 斜率优化 DP（CHT）
- 树形 DP
- 树的直径个数
- 在任一直径上的节点个数
- 树上最大独立集
- 树上最小顶点覆盖
- 树上最小支配集
- 树上最大匹配
- 换根 DP（二次扫描法）
- 背包
- 图论 graph.go
- 链式前向星
- 欧拉回路和欧拉路径
- 无向图
- 有向图
- 割点
- 割边（桥）
- 双连通分量（BCC）
- v-BCC
- e-BCC
- 最短路
- Dijkstra
- SPFA（队列优化的 Bellman-Ford）
- 差分约束系统
- Floyd-Warshall
- Johnson
- 0-1 BFS（双端队列 BFS）
- 字典序最小最短路
- 最小环
- 最小生成树（MST）
- Kruskal
- Prim
- 单度限制最小生成树
- 次小生成树
- 曼哈顿距离最小生成树
- 最小差值生成树
- 最小树形图
- 朱刘算法
- 二分图判定（染色）
- 二分图找奇环
- 二分图最大匹配
- 匈牙利算法
- 带权二分图最大完美匹配
- Kuhn–Munkres 算法
- 拓扑排序
- 强连通分量（SCC）
- Kosaraju
- Tarjan
- 2-SAT
- 基环树
- 最大流
- Dinic
- ISAP
- HLPP
- 最小费用最大流
- SPFA
- Dijkstra
- 三元环计数
- 四元环计数
- 仙人掌
- 树上问题 graph_tree.go
- 直径
- 重心
- 点分治
- 最近公共祖先（LCA）
- 倍增
- ST 表
- Tarjan
- 树上差分
- 树链剖分（重链剖分，HLD）
- 长链剖分
- 树上启发式合并（DSU）
- 树分块
- Prufer 序列
- 其他
- 位运算笔记 bits.go
- bitset
- 区间位运算 trick（含 GCD）
- 二分 三分 sort.go
- 0-1 分数规划
- 整体二分
- 搜索 search.go
- 枚举排列
- 枚举组合
- 生成下一个排列
- 康托展开
- 逆康托展开
- 折半枚举
- 超大背包问题
- 枚举子集
- Gosper’s Hack
- 随机算法 rand.go
- 模拟退火
- 杂项A common.go
- 算法思路整理
- 前缀和
- 离散化
- 杂项B misc.go
- 位运算笔记 bits.go
- 快读模板 io.go
如何选择题目 How to Choose Problems
Rating < 2100
这一阶段主要目标是提高对问题的观察能力。做构造题可以针对性地训练这一点。
选择难度在自己 rating 到 rating+200 范围内的构造题 (tag: constructive algorithms)，按照过题人数降序做题，比如 [1700,1900] 区间的就是下面这个链接：
https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=constructive+algorithms%2C1700-1900
通过大量的构造题训练，提高观察能力，快速找到切题入口。
Rating >= 2100
这一阶段要想上分，应以 DP 为主，图论和数据结构为辅。难度范围选择同上，可以根据自己在该项的能力上下调整。
我的 Codeforces 账号：
测试及对拍 Testing
编写一个 run(io.Reader, io.Writer) 函数来处理输入输出。这样写的理由是：
- 在
main中调用run(os.Stdin, os.Stdout)来执行代码； - 测试时，将测试数据转换成
strings.Reader当作输入，并用一个strings.Builder来接收输出，将这二者传入run中，然后就能比较输出与答案了； - 对拍时需要实现一个暴力算法
runAC，参数和run一样。通过随机数据生成器来生成数据，分别传入runAC和run，通过比对各自的输出，来检查run中的问题。
具体可以见 Codeforces 代码仓库 main，所有非交互题的代码及其对应测试全部按照上述框架实现。
交互题的写法要复杂一些，需要把涉及输入输出的地方抽象成接口，详见 interactive_problem。
学习资料及题目 Resources
注：由于入门经典上选了很多区域赛的题，一部分题目可以在 GYM 上找到，这样可以就可以用 Go 编程提交了。
算法竞赛 (ICPC, OI, etc) 论文，课件，文档，笔记等
All the good tutorials found for Competitive Programming
Links of ICPC/CCPC Contests from China
高级竞赛算法
AtCoder 版《挑战程序设计竞赛》
待整理
https://blog.csdn.net/calabash_boy/article/details/79973483
https://github.com/zimpha/algorithmic-library
https://www.luogu.com.cn/blog/command-block/blog-suo-yin-zhi-ding-post
https://www.luogu.com.cn/blog/Troverld/index
其他 Others
My GoLand Live Templates and Postfix Completion settings
Useful Tools
Another Codeforces Solve Tracker
Rating and Difficulties
How to Interpret Contest Ratings
Codeforces: Problem Difficulties
Directories