T1 题目描述 这是 SA 酱 (angel ver.) 的卡面介绍. SA 酱现在有一个长 $n$ 的序列 $a_1,\dots,a_n$，初始时候 $a_i=i$. 定义序列的价值为 $(a_1\oplus 1)+(a_2\oplus 2)+\dots+(a_n\opl...

1994 字 丨 6.6分钟

问题引入 如果我们需要一种算法，使其可以将一个字符串的所有子序列表示为一个 DAG（即有向无环图），我们该如何构建？ 构建 钦定 $n$ 为字符串的长度，$\Sigma$ 为字符集，$S$ 为字符串，且 $S$ 只会包含小写字母。 我们定义 $nxt_ (i \leq ...

3578 字 丨 11.9分钟

优化建图是一种图论中的辅助方法，通过建辅助点的方法将图优化，通常，这可以大幅度减少算法的时间复杂度和空间复杂度。 例题 檀香梅 题解 这道题如果使用传统的直接建图，则一共有 $O(n^2)$条边，在 TLE 之前就已经 MLE 了，所以我们考虑到使用其他方法。 考虑到这道题...

2834 字 丨 9.4分钟

考虑下面的这个问题： www.luogu.com.cn 显然，这是一道最短路，但是直接建图肯定会 $TLE$，相当于你要把 $l$ 到 $r$ 之内的点全部连一条边，这样单次操作的事件复杂度是 $O(n)$ 的，所以，我们需要考虑一种聪明的方式来优化它。 考虑到这是一堆区间...

3819 字 丨 12.7分钟

问题引入 假如我们要用一个有向无环图存一个字符串的所有子串，然后跑各种图论中的算法，以 $abaab$ 为例，该怎么做 SAM介绍 注意到，这种方法的时间在最劣的情况下是 $O(n^2)$ 的，因为其中还有很多部分可以优化 观察到 $a→a→b...

8978 字 丨 29.9分钟