后缀数组

模版 代码 struct SA { int n, sa[maxn], rk[maxn<<1], oldrk[maxn<<1], cnt[maxn], id[maxn], key1[maxn], height[maxn]; // 注意 rk[maxn<<1] oldrk[maxn<<1] char s[maxn]; int m = 127; bool cmp(int i, int j, int w) { return oldrk[i] == oldrk[j] && oldrk[i+w] == oldrk[j+w]; } void init(string& ss) { n = ss.size(); // LOG(n); for (int i = 1; i <= n; i++) s[i] = ss[i-1]; for (int i = 1;

二维ST表

介绍 二维ST表就是在一维的ST表上加一个维度,这样可以 $O(nm\log n \log m)$ 内预处理以后,$O(1)$ 询问一个矩阵的最大/最小值。 例题 例1 洛谷P2216[

Universal Cup 8 (Slovenia)

C. Constellations 题意 二维平面中有 $n$ 个点,一开始每个点都属于自己的一组。 有 $n-1$ 轮合并过程,每次合并选择距离最近的两组点进行合并,两组点 $A,B$ 之间的距离定义为: $$d(A,B)

二项式反演

介绍 二项式反演是一种特殊的容斥,用来解决 “恰好选 $k$ 个的方案有多少种” 的问题。 一般,我们可以求出 “至多/至

NAC2022

G. Rafting Trip 题意 给定一个 $n \times m$ 的网格,每个网格要么是河流,要么是陆地。 如果是河流,那么它一定是上下左右四个方向之一,代表走到这个位置,下一个位置就

01BFS 最短路

老是忘,简单记录一下吧。 介绍 一个边权仅为 $0,1$ 的图中跑最短路可以直接用 bfs。 维护一个 deque,每次更新 dis[v] 时就将 v push进去,如果 w(u,v) == 0 就p

三元环计数

介绍 给定一个无向图,找出图中所有的三元环,每个环只能被计一次。(比如 $a,b,c$ 和 $b,a,c$ 都是同一个环)。 我们先处理出每个点的 degree,然后建一个新的图

博弈论与SG函数

公平组合游戏 公平组合游戏 Impartial Combinatorial Game (ICG) 满足以下性质: 有 $2$ 名玩家。 $2$ 名玩家轮流操作,在一个游戏集合中选其中一个进行操作。 对于任意一个合法的局面,当前