mmr256@hznu

ax_by_c · 2026-03-08 21:29:08 · 生活·游记

本来写的挺好了的，但是没心情发出来了。

又炸了一个题，我已经无所谓了。

反正不是高二，明年再来吧。

可能另一个时空我已经打到 340+212+136 甚至更高了，要是这都进不去可能真要退役了。

补几个题解，不一定是我拿到了的分数。

找寻者

问题关键在于算出以 i 为顶端链长为 j 的概率 f_{i,j}。枚举取得的儿子及链长，根据小学数学有 \frac{a}{c}=\frac{a}{b}\frac{b}{c}，启发我们先和前面合起来再和后面合起来。设 F_{i,j} 为前 i 个儿子总链长为 j 的概率，G_{i,j} 为前 i 个儿子总链长为 j 且最后选了前 i 个儿子中的一个的概率，不难做到 O(n^2)。

摩卡串

考虑从前往后直接 dp。由于需要处理匹配上个 kmp 自动机，然后考察以 border 前面位置为开头的子串的字典序贡献。由于它们匹配不上所以贡献形式已经确定了，一定是每次 pushback 时不贡献或者一定贡献，border 部分贡献可以暴力预处理。于是 $f{i,j,k,0/1} 表示当前 border 长度，当前字典序 <s 子串数，当前 border 之前一定贡献的开头个数，以及是否完整匹配过 s，时的最小长度。注意到 j=O(k^2)，因此时间复杂度 O(nm^{\frac{3}{2}})$。

排列游戏

当 l,r 中没有 0 是无意义的，因此先找出 0 的位置 p。考虑询问 \forall_{i\in[0,p]}query(i,n-1),\forall_{i\in[p,n-1]}query(0,i)。不难发现此时若干数位置被确定，其余数位置被限制在一个区间中，且越小的数限制越紧，直接从小到大填空即可。至于次数限制随便卡卡就进了。