Mivik 展开(大雾
OI 知识点汇总
关于广义后缀自动机

关于广义后缀自动机

约束

tar[x][c]:SAM 转移

pre[x]:常用名有 linkfail(反正就那个东西)

len[x]:结点 x 代表的最长字符串的长度


广义后缀自动机(下文用广义 SAM 指代),即用多个字符串的后缀建出的一个后缀自动机,拥有和后缀自动机相似的性质。

有三种较流传广泛的广义后缀自动机写法:

阅读更多
分数规划/01规划

分数规划/01规划

今天也是Mivik被智商碾压的一天啊QwQ

分数规划 貌似 和01规划是一个东西吧QwQ

问题

我们现在要求这样一个式子的最大值

$$
\frac{\sum e_i.a}{\sum e_i.b}
$$

其中 $e$ 中的元素是可以选择的,且 $e_i.a > 0$ ,$ e_i.b > 0$

阅读更多