两个简单题 + 一个比较难的原题.
$Gene$
有一个十分简单的 $O(n\log n)$ 的做法,字符串 $hash$ + 二分,用自然溢出常数比较小,是可以过的.
$O(n)$ 的一个做法是 $SAM$ ,对反串建后缀自动机,答案就是每个点的 $siz$ 之和,但空间很容易炸.
另一个做法是利用 $kmp$ 的 $fail$ 数组,每个位置不断往前跳,每跳一次就说明有一个合法的匹配.
暴力跳会超时,记忆化一下,用 $f(i)$ 表示从 $i$ 开始能往前跳几次,则 $f(i)=f(fail_i)+1$ .
$Shield$
因为给出的两个向量线性无关,可以它们为一组基底,解出每个点在这组基底下的坐标.
于是一个点可以转移到 $x,y$ 都不小于它的点.
将点按 $x$ 为第一关键字, $y$ 为第二关键字排序,将 $y$ 离散化后用树状数组做一个类似于 $LIS$ 的 $dp$ 即可.
时间复杂度 $O(n\log n)$ .
坐标太大,精度爆掉了一个点.其实可以在比较元素时再转换坐标,避免小数运算.
$Chronosphere$
首先可以建出源汇点 $S,T$ ,源点向所有点连边,所有点向汇点连边.
问题转化为最小化删去一个点后 $S\to T$ 的最长路长度.
拓扑排序 + $dp$ 处理出 $f(i),g(i)$ 分别表示 $S\to i$ 的最长链与 $i\to T$ 的最长链经过的点数.
那么对于一条边 $u\to v$ ,它的的贡献就是 $f(u)+g(v)-1$ .
若有一个 $S\to T$ 的割,那么所有 $S\to T$ 路径一定会经过至少一条割集中的边,只需要考虑割集中的边贡献.
一开始让 $s$ 集只有 $S$ , $T$ 集包含剩余的所有点,这是一个合法的割.
按照拓扑序枚举删掉 $x$ 后的答案,依次进行如下操作,以将点 $x$ 从 $T$ 集合中取出,放入 $S$ 集中.
$1.$ 将 $x$ 的所有入边从割集中删掉.
$2.$ 所有割集的边的最大贡献就是删掉点 $x$ 的答案.
$3.$ 将 $x$ 的所有出边加入割集.
正确性可以利用数学归纳法证明.
执行第 $1$ 步之前,割是整张图的一个割,假设它不含从 $x$ 出发能到的任何边.
所以删掉 $x$ 的入边后,割就是去掉 $x$ 的图的一个合法割,此时可以更新答案.
若将 $x$ 放回图中, $S\to T$ 的路径就一定经过 $x$ ,所以割掉 $x$ 的所有出边,又成了一个合法割.
因为是按照拓扑序依次处理的,所以加入的 $x$ 的入边在之后一定不能被到达,满足了先前的假设.
而初始状态也是满足假设的,所以可以归纳证得以上算法的正确性.
割集只需要记录边的贡献,不记录边的编号,所以可以用一棵权值线段树进行维护,时间复杂度 $O(m\log m)$ .