某島

… : "…アッカリ~ン . .. . " .. .
June 30, 2021

Atcoder 演算法庫

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 下取整的和。(這玩意居然也需要進模板?)
$$\sum_{i = 0}^{N – 1} \lfloor(A \times i + B) / M\rfloor$$

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

import sys
from atcoder.maxflow import MFGraph
I = lambda: [int(x) for x in input().split()]

n, m = I()
s = 2*n
t = s+1
G = MFGraph(t+1)
a = I()
b = I()
z = 0

for i in range(n):
    bb = abs(b[i])
    z += bb
    G.add_edge(i, i+n, a[i] + bb)
    bb *= 2
    if (b[i] < 0):
        G.add_edge(i+n, t, bb)
    else:
        G.add_edge(s, i, bb)

for i in range(m):
    x, y = I()
    x -= 1
    y -= 1
    G.add_edge(x+n, y, sys.maxsize)
    G.add_edge(y+n, x, sys.maxsize)

print(z-G.flow(s,t))

E – MinCostFlow

最小費用最大流
https://atcoder.jp/contests/agc034/tasks/agc034_d

F – Convolution

FFT 卷積

G – SCC

強連通分量

H – Two SAT

2SAT

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

懶標記線段樹