LuoguLOJ分析首先容斥一下,求出三段都不包含 $s_{l..r}$ 的方案数,然后用 ${n-1\choose 2}$ 减掉即为答案。我们先把所有和 $s_{l..r}$ 相等的子串位置都找到,然后分类讨论一下:如果有三个互不相交的串,方案数是 $0$。如果最左边的串和最右边的串相交:考虑 $i$ 的位置:如果 $i\in[1,l_1)$,那么 $j\in(l_m,r_1]$,方案数为...
LuoguLOJ分析首先把第 $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}$ 的最高次项都是 $x^n...
LuoguLOJ分析规定根节点的深度为 $1$。考虑 DP。设 $dp_{u,i}$ 表示以 $u$ 为根的子树,下端在子树中的未被覆盖的链的上端的最深深度为 $i$ 时的方案数($i=0$ 表示全部被覆盖)。这个“最深”的好处在于我们覆盖了深的就一定会覆盖浅的,便于计数。考虑转移,每次把一棵子树合并进来,考虑子树的父边填 $1$ 还是 $0$ 可以得到可以想到整体 DP,用线段树维护每个节...
Conspiracy考虑如果已经有了一组方案怎么得到其它的方案,可以发现只有以下三种情况:团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。于是考虑构造一组方案。注意到每个点只能在团内或团外,于是 2-SAT 即可。可能会有些卡空间。代码Lollipop可以发现如果存在一段和为 $w$,则一定存在一段和为 $w-2$,...
CodeforcesLuogu分析容易想到一个 DP。设 $dp_u$ 表示 $u$ 跳到叶子节点的最小花费,显然有转移可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑李超线段树,转移时直接查询对应位置的最小值,然后向上合并即可。可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑...
LuoguLOJ分析先考虑 $l=1,r=|S|$ 的情况。对 $S$ 和 $T$ 建 SAM。设 $lim_i$ 表示 $T[1..i]$ 最长的是 $S$ 的子串的后缀的长度,可以在 $S$ 的 SAM 的 Parent 树上跳来求出:如果有对应的转移直接走过去,匹配长度加 $1$;否则跳 Parent 树,直到某个点有对应的转移,匹配长度变为该点的 $len$;如果跳到 $1$ 都没有...
998244353?998244353!
Luogu分析线段树合并。显然只有两种情况: $a$ 比 $b$ 不知道高明到哪去了、 $b$ 比 $a$ 不知道高明到哪去了。第二种比较简单。设 $a$ 的深度为 $dep[a]$ ,子树大小为 $sz[a]$ ,答案就是 $\min\{dep[a]-1,k\}\times (sz[a]-1)$ 。第一种的话,可以在 $a$ 的子树中随便选一个点和 $a$ 谈笑风生的点作为 $b$ ,然后...
LuoguBZOJ分析并查集+线段树合并。考虑怎么求出一个连通块内的第 $k$ 大值。如果有一颗对应的权值线段树,就可以很方便的求出来了。那么考虑怎么搞出这颗权值线段树。一开始对于每个点维护一颗线段树,每次合并两个连通块时,直接线段树合并即可。具体实现及细节见代码。代码//It is made by M_sea #include <algorithm> #include <...