Atcoder 算法库
source link: http://www.shuizilong.com/house/archives/atl/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Atcoder 算法库（ACL） 出了快一年了，一直没仔细看，这两天写 《天才算法少女》 的主线剧情，正好复习一下这个。不过这玩意更新的着实挺慢的，还没我的 Template 算法多。。。不过至少可以和 rng_58 学习一下怎么写 test 。。。
首先讲一下怎么像 STL 一样加入 cpp 的默认头文件，方法当然是编辑编译器的 Search directories。这个库结构非常简单，对于不支持 ACL 的 OJ，估计也可以手动展开一下。
为了推广这个库，rng_58 还准备了两场 ACL contest，用来测试模板。当然这个东西的适用范围还有待观察，毕竟模板的缺点是不能进去魔改，最典型的缺陷可能就是无法给 std::set<int> 里的二叉树节点加卫星数据 size 以实现求第 kth 大这种实用操作。。。？。。。（比如需要加卫星数据的并查集可能也没法搞了）
A – Disjoint Set Union
并查集
– https://vjudge.net/problem/AtCoder-abc181_f
B – Fenwick Tree
C – Floor Sum
等差数列每一项除以 M 下取整的和。（这玩意居然也需要进模板？）
∑i=0N–1⌊(A×i+B)/M⌋
D – Maxflow
最大流
– https://vjudge.net/problem/AtCoder-agc038_f
– https://atcoder.jp/contests/arc107/tasks/arc107_f
– https://atcoder.jp/contests/abc193/tasks/abc193_f
E – MinCostFlow
最小费用最大流
– https://atcoder.jp/contests/agc034/tasks/agc034_d
F – Convolution
FFT 卷积
G – SCC
强连通分量
H – Two SAT
I – Number of Substrings
后缀数组
里面的实现用的是 sa-is 线性构造算法。
– https://atcoder.jp/contests/abc141/submissions/23884310
– https://atcoder.jp/contests/arc097/tasks/arc097_a
J – Segment Tree
K – Range Affine Range Sum
懒标记线段树
L – Lazy Segment Tree
懒标记线段树
Posted by
xiaodao
Category: 日常
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK