由于算法知识点繁杂,将自己学习到的算法、做过的题目分类整理好是有必要的。
一个算法模板应当涵盖以下几点:
- 对该算法的基本介绍(核心思想、复杂度等)
- 参考链接或书籍章节(讲得比较好的资料)
- 模板代码(代码注释、使用说明)
- 模板补充(常见题型中的额外代码、建模技巧等)
- 相关题目(模板题、经典题、思维转换题等)
- 集合论与位运算
- 数据结构
- 单调栈 monotone_stack.go
-
单调队列 monotone_queue.go
- 二维单调队列
- 双端队列 deque.go
-
堆(优先队列)heap.go
- 支持修改、删除指定元素的堆
- 懒删除堆
- 对顶维
- 前缀中位数
- 滑动窗口前 k 小元素和
-
并查集 union_find.go
- 点权并查集
- 边权并查集(种类并查集)
- 可持久化并查集
- 回滚并查集 & 动态图连通性
- 稀疏表(ST 表)sparse_table.go
-
树状数组 fenwick_tree.go
- 差分树状数组(支持区间加、区间求和)
- 二维差分树状数组
- 树套树 & 三维偏序
-
线段树 segment_tree.go
- 线段树二分
- 延迟标记(懒标记)
- 动态开点
- 线段树合并
- 线段树分裂
- 持久化(主席树)
- 0-1 线段树 segment_tree01.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
- pi 函数
- border
- 最小循环节
- fail 树(失配树 / border 树)
- 扩展 KMP(Z algorithm)
- 最小表示法
- 最长回文子串
- Manacher 算法
- 回文自动机(回文树,PAM)pam.go
- 后缀数组(SA)
- 后缀自动机(SAM)sam.go
-
字典树 trie.go
- 可持久化字典树
-
0-1 字典树 trie01.go
- 最大异或和
- 第 k 大异或和
- 删除元素
- 可持久化 0-1 字典树
- 【研究】0-1 字典树上最多有多少个节点
- AC 自动机 acam.go
- 数学
-
数论 math.go
- 辗转相除法(最大公因数 GCD)
- 类欧几里得算法 ∑⌊(ai+b)/m⌋
- Pollard-Rho 质因数分解算法
- 埃氏筛(埃拉托斯特尼筛法)
- 欧拉筛(线性筛)
- 欧拉函数
- 原根
- 扩展 GCD
- 二元一次不定方程
- 逆元
- 线性求逆元
- 中国剩余定理(CRT)
- 扩展中国剩余定理
- 离散对数
- 大步小步算法(BSGS)
- 扩展大步小步算法
- 二次剩余
- Jacobi 符号
- N 次剩余
- 卢卡斯定理
- 扩展卢卡斯定理
- 卡特兰数
- 默慈金数
- 那罗延数
- 斯特林数
- 第一类斯特林数(轮换)
- 第二类斯特林数(子集)
- 贝尔数
- 欧拉数
- 数论分块(整除分块)
- 莫比乌斯函数
- 莫比乌斯反演
- 互质计数问题
- GCD 求和问题
- 杜教筛
-
组合数学 math_comb.go
- 常见模型
- 常用恒等式
- 容斥原理
- 快速傅里叶变换 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
- 线与点
- 线与线
- 圆与点
- 最小圆覆盖
- Welzl 随机增量法
- 固定半径覆盖最多点
- 最小圆覆盖
- 圆与线
- 圆与圆
- 圆与矩形
- 最近点对
- 多边形与点
- 判断点在凸多边形内
$O(\log n)$ - 判断点在任意多边形内
- 转角法(统计绕数)
- 判断点在凸多边形内
- 凸包
- 最远点对
- 旋转卡壳
- 半平面交
-
博弈论 games.go
- SG 函数
-
数论 math.go
-
动态规划 dp.go
- 背包
- 0-1 背包
- 完全背包
- 多重背包
- 二进制优化
- 单调队列优化
- 同余前缀和优化(求方案数)
- 分组背包
- 树上背包(依赖背包)
- 字典序最小方案
- 线性 DP
- 最大子段和
- LCS
- LPS
- LIS
- 狄尔沃斯定理
- LCIS
- 长度为 m 的 LIS 个数
- 本质不同子序列个数
- 区间 DP
- 环形 DP
- 博弈 DP
- 概率 DP
- 期望 DP
- 状压 DP
- 全排列 DP
- 旅行商问题(TSP)
- 子集 DP
- 高维前缀和(SOS DP)
- 插头 DP
- 数位 DP
- 记忆化搜索(同时跑上下界)
- 倍增优化 DP
- 斜率优化 DP(CHT)
- WQS 二分优化 DP(凸优化 DP / 带权二分)
- 树形 DP
- 树的直径个数
- 在任一直径上的节点个数
- 树上最大独立集
- 树上最小顶点覆盖
- 树上最小支配集
- 树上最大匹配
- 换根 DP(二次扫描法)
- 简单写法
- 维护最大次大写法
- 前后缀分解写法(适用性最广)
- 背包
-
图论 graph.go
- 链式前向星
- DFS 常用技巧
- BFS 常用技巧
- 欧拉回路和欧拉路径
- 无向图
- 有向图
- 完全图
- 割点
- 割边(桥)
- 双连通分量(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)
- 长链剖分
- 树上启发式合并(small to large)
- 按大小合并
- 轻重儿子合并
- 树分块
- Prufer 序列
- 其他
-
位运算笔记 bits.go
- bitset
- 区间位运算 trick(含 GCD)
-
二分 三分 sort.go
- 二分答案
- 0-1 分数规划
- 整体二分
-
搜索 search.go
- 枚举排列
- 枚举组合
- 生成下一个排列
- 康托展开
- 逆康托展开
- 枚举子集
- Gosper's Hack
- 折半枚举(Meet in the middle)
- 超大背包问题
-
随机算法 rand.go
- 模拟退火
-
基础算法 common.go
- 算法思路整理
- 分组循环
- 滑动窗口
- 前缀和
- 同余前缀和
- 二维前缀和
- 菱形区域和
- 斜向前缀和
- 菱形边界和
- 等腰直角三角形区域和
- 金字塔区域和
- 二阶差分
- 二维差分
- 菱形二维差分
- 离散化
- 杂项 misc.go
-
位运算笔记 bits.go
- 快速输入输出模板 io.go
- 交互题单 interactive.go
- 滑动窗口与双指针(定长/不定长/单序列/双序列/三指针)
- 二分算法(二分答案/最小化最大值/最大化最小值/第K小)
- 单调栈(基础/矩形面积/贡献法/最小字典序)
- 网格图(DFS/BFS/综合应用)
- 位运算(基础/性质/拆位/试填/恒等式/思维)
- 图论算法(DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径)
- 🔥动态规划(入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望)
- 常用数据结构(前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树)
- 数学算法(数论/组合/概率期望/博弈/计算几何/随机算法)
- 贪心与思维(基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造)
- 链表、二叉树与回溯(前后指针/快慢指针/DFS/BFS/直径/LCA/一般树)
- 字符串(KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机)
欢迎关注 B站@灵茶山艾府
这一阶段主要目标是提高对问题的观察能力。做构造题可以针对性地训练这一点。
选择难度在自己 rating 到 rating+200 范围内的构造题 (tag: constructive algorithms),按照过题人数降序做题,比如 [1700,1900] 区间的就是下面这个链接:
https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=constructive+algorithms%2C1700-1900
通过大量的构造题训练,提高观察能力,快速找到切题入口。具体见我在知乎上的这篇 回答。
见识更高的山、更广的海。
按人数从高到低,做 2200+ 的题目。建议不设置难度上限!由于按人数排序,难度分不会太高,不设上限可以避免错过高分好题。
- 按照洛谷通过人数排序的 CF 题单
- 构造题 2200+:锻炼手玩能力。
- DP 2200+:几乎每场都有 DP。
- 数学综合:数论、组合数学、概率期望等 2200+:包含 6 个 tag。
- 图论综合:图论+树上问题 2200+:包含 7 个 tag。
- 字符串 2200+:数据结构题不好筛选,可以找树状数组/线段树的题单,这里只单独筛选字符串的题。
- 交互 2200+:偶尔做做,了解一些解题套路。
- 博弈 2000+:也适合锻炼手玩。由于题目比较少,从 2000 开始筛选。
我的 Codeforces 账号
编写一个 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。
注:由于入门经典上选了很多区域赛的题,一部分题目可以在 GYM 上找到,这样可以就可以用 Go 编程提交了。
算法竞赛 (ICPC, OI, etc) 论文,课件,文档,笔记等
The Ultimate Topic List (with Resources, Problems and Templates)
A Huge Update on The Ultimate Topic List
All the good tutorials found for Competitive Programming
The Ultimate Topic List(with Tutorials, Problems, and Templates)
https://github.com/hh2048/XCPC 含 jiangly 模板
https://www.cnblogs.com/alex-wei/p/contents.html
Links of ICPC/CCPC Contests from China
[meme] If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
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
My GoLand Live Templates
and Postfix Completion
settings
Another Codeforces Solve Tracker
AtCoder-Codeforces Rating converter
How to Interpret Contest Ratings