CF666E Forensic Examination
Codeforces Luogu 分析 先对 $T_{1..m}$ 建立广义 SAM，然后把 $S$ 丢上去匹配，记录每个前缀匹配到的节点 $pos_i$。 考虑对每个节点维护一棵以 $T$ 的下标为下标的线段树，线段树上的每个节点维护当前串在这些 $T$ 串中的出现次数的最大值及其下标。这可以通过线段树合并预处理出来。 询问时，我们首先找到 $s_{l..r}$ 所在的节点，直接从 $po...
标签 线段树合并 下的文章
- 首页
- 线段树合并
洛谷4384 [八省联考2018]制胡窜
Luogu LOJ 分析 首先容斥一下，求出三段都不包含 $s_{l..r}$ 的方案数，然后用 ${n-1\choose 2}$ 减掉即为答案。 我们先把所有和 $s_{l..r}$ 相等的子串位置都找到，然后分类讨论一下： 如果有三个互不相交的串，方案数是 $0$。 如果最左边的串和最右边的串相交： 考虑 $i$ 的位置： 如果 $i\in[1,l_1)$，那么 $j\in(l_m,...
洛谷4365 [九省联考2018]秘密袭击coat
Luogu LOJ 分析 首先把第 $k$ 大转化掉： 不妨再设一个 $g_{i,j,k}$ 表示子树 $f_{i,j,k}$ 的和，并设 $G_{i,j}(x)=\sum_k g_{i,j,k}x^k$。答案即为 $\sum_{i=k}^n[x^i](\sum_j G_{1,j})$。 看起来这个转移并没有什么可以优化的地方。但是 $F_{i,j}$ 和 $G_{i,j}$ 的最高次项都...
洛谷6773 [NOI2020]命运
Luogu LOJ 分析 规定根节点的深度为 $1$。 考虑 DP。设 $dp_{u,i}$ 表示以 $u$ 为根的子树，下端在子树中的未被覆盖的链的上端的最深深度为 $i$ 时的方案数（$i=0$ 表示全部被覆盖）。这个“最深”的好处在于我们覆盖了深的就一定会覆盖浅的，便于计数。 考虑转移，每次把一棵子树合并进来，考虑子树的父边填 $1$ 还是 $0$ 可以得到 可以想到整体 DP，用线...
POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
CF932F Escape Through Leaf
Codeforces Luogu 分析 容易想到一个 DP。设 $dp_u$ 表示 $u$ 跳到叶子节点的最小花费，显然有转移 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑李超线段树，转移时直接查询对应位置的最小值，然后向上合并即可。 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。...
洛谷4770 [NOI2018]你的名字
Luogu LOJ 分析 先考虑 $l=1,r=|S|$ 的情况。 对 $S$ 和 $T$ 建 SAM。 设 $lim_i$ 表示 $T[1..i]$ 最长的是 $S$ 的子串的后缀的长度，可以在 $S$ 的 SAM 的 Parent 树上跳来求出： 如果有对应的转移直接走过去，匹配长度加 $1$； 否则跳 Parent 树，直到某个点有对应的转移，匹配长度变为该点的 $len$； 如果跳...