带星号(*)的为参考模板。
PART1 排序
status | Name | Problem Link | |
---|---|---|---|
OK(OK==已完成) | 快速排序 | 洛谷P1177 | |
OK | 归并排序 | 同上 | |
OK | 堆排序 | 同上 | |
OK | STL优先队列 | 洛谷P1334 |
PART2 树及线性区间问题
status | Name | Problem Link | More | |
---|---|---|---|---|
OK(OK==已完成) | LCA(ST倍增) | 洛谷P3379 | 在线 | |
OK | LCA(Tarjan) | 同上 | 离线 | |
OK | LCA(树链剖分) | 洛谷P3379 | 我不知道在线离线 | |
OK | RMQ(ST表) | 洛谷3865 | ||
OK | 差分计算 | 洛谷3948 | ||
OK | 树状数组 | 洛谷P3374/洛谷P3368 | 第2题为差分树状数组 | |
OK | 线段树 | 洛谷P3372/洛谷P3373 | 第二题为二维线段树 | |
OK | 树链剖分 | 洛谷P3384 | ||
OK | 平衡树Treap | 洛谷P3369 | 数组实现的平衡树 | |
OK | 平衡树的STL实现:set和multiset参考1、参考2 | |||
*OK | FHQ-Treap | 洛谷P3369 | 简单全能的平衡树实现参考 |
PART3 图
status | Name | Problem Link | more | |
---|---|---|---|---|
OK(OK==已完成) | SP:Floyd | n极小时适用 | ||
OK | SP:Bellman-Ford | O(NM) | ||
OK | SP:SPFA+SLF+LLL优化 | 洛谷P3371 | 可处理负边,检测负环 | |
OK | SP:优先队列优化的Dijkstra | 洛谷P4779 | 通常具有最佳效率,适用于非负权图 | |
OK | MST:Prim | 洛谷P3366 | 附pair用法 | |
OK | MST:Kruskal | 同上 | ||
OK | 拓扑排序 | 洛谷P1137 | ||
OK | SCC:Tarjan | 洛谷P2002 | ||
OK | SCC:Kosaraju | 洛谷P2002 | ||
OK | 找负环 | 洛谷P3385 | ||
OK | 差分约束 | 洛谷P1993/洛谷P3275 | 含讲解 | |
OK | 欧拉回路 | 洛谷P2731/洛谷P1341 | 简单证明、两种算法讲解 | |
OK | 割点和桥 | 洛谷P3388 | 割点讲解 | |
OK | 01最短路 | 洛谷P1948 |
PART4 数学
status | Name | Problem Link | |
---|---|---|---|
OK(OK==已完成) | 埃式筛法 | 洛谷P3912 | |
OK | 欧拉线性筛以及欧拉函数 | 洛谷P3383 | |
OK | 拓展欧几里德 | ||
OK | 快速幂 | 洛谷P6685 | |
OK | 随机数生成 |
PART5 其它
status | Name | Problem Link | more | |
---|---|---|---|---|
OK(OK==已完成) | 快读 | 用于大量数据读入时 | ||
OK | 并查集 | 洛谷P3367,洛谷P1525 | ||
OK | 字符串哈希 | 洛谷P3370,LOJ.ac103 | 参考文章 | |
OK | 哈希表 | LOJ.ac10034 | 参考文章 | |
OK | KMP算法 | 洛谷P3375 | 参考文章1、参考文章2 | |
OK | Trie字典树 | LOJ.ac10049、洛谷P2292、LOJ.ac10054 | 参考文章1、参考文章2 | |
OK | AC自动机 | 洛谷P3808、洛谷P3796、洛谷P5357 | 参考文章1、参考文章2 | |
OK | 模拟退火 | 洛谷P1337 |
省选模板区
status | Name | Problem Link | more | |
---|---|---|---|---|
OK(OK==已完成) | 可持久化并查集 | 洛谷P3402 | ||
文艺平衡树SPlay | 洛谷P3835 | |||
可持久化平衡树 | 洛谷P3391 | |||
二分图染色 | 洛谷P1234 | |||
OK | 二分图匹配(匈牙利算法) | 洛谷P3386 | Capella提供 | |
网络流 | ||||
最小割 |
2020.12 update by Nw 添加了数学中的代码与一些杂项,所以一些链接中的码风会与其他不同,有问题欢迎反馈