2022.8.6 模拟赛

T1 escape

  字典序最小，所以考虑贪心。

  从小到大枚举每一个位置，再枚举从小到大每一个字母，看这个字母后面有没有，如果有判断它移到这个位置的步数（用树状数组区间加实现），如果可以那么 $k-=step$。

  复杂度大概就是 $O(n\log n)$ 的。

T2 ride

  注意到有很多部分分，所以可以考虑每一种图怎么骗分。但是由于这个正解也比较简单，所以就直接说正解了，部分分今天写完有空再写吧。

  对于点 $x$ 令 $f_{x,i}$ 表示以这个点为根，到它的第 $i$ 颗子树中的海拔下降的路径的条数，那么这个点的贡献就是（子树个数为 $k$）：

$$2(\sum _{i=1}^k\sum _{j=1}^k{f}_{x,i}{f}_{x,j})={\left(\sum _{i=1}^k{f}_{x,i}\right)}^2-\sum _{i=1}^k{f}_{x,i}^2$$

  然后就树形 $dp$，转移就是：

$$f_x=\sum _{y\in Sun(x)\wedge y<x}(f_y+1)$$

  这里面有一个条件 $y<x$ 所以我们考虑按照海马顺次递增枚举计算贡献，然后就做完了。

T3 road

  我们考虑 $x\to y$ 存不存在距离为 $d$ 的路径（不一定是简单路径）。

  假设我们找到了一条 $x\to y$ 的最短路，长度为 $len$，那么我们考虑在这条最短路的某两个点上反复横跳来延长路径长度。

  这样一来，我们发现延长的路径长度一定是偶数，所以如果 $len$ 和 $d$ 奇偶性相同，那么就一定存在一条路径从 $x\to y$ 长度为 $d$。

  所以我们维护一个 数组 $di{s}_{x,y,k}$ ，其中 $k$ 等于 $0$ 或者 $1$。$k=0$ 时表示是否存在路径长度为偶数的最短路的长度，$k=1$ 表示是否存在路径长度为奇数的最短路的长度。那么存在长度为 $d$ 的路径当且仅当：

$$di{s}_{x,y,d\mathrm{mod}2}\le d$$

  时间复杂度 $O(n^2)$。

T4 tree

$n\le 10$

  首先时前 $20pts$，就暴力搜索然后 $O(\log n)$ 求距离，令 $f_n$ 表示匹配方案数，那么时间复杂度时 $O(n{f}_n\log n)$。

菊花图

  然后 $40pts$ 做菊花图，我们发现对于菊花图来说，所有方案的 $\sum _{i=1}^{\frac{n}{2}}{d}_i$ 都是相同的。因为都是有一个点和最中间的点配对，然后其它点两两配对所以是：

$$\sum _{i=1}^{\frac{n}{2}}{d}_i=1+\frac{n-2}{2}\times 2=n-1$$

  然后答案就应该是 $(n-1)f_n$，所以我们考虑怎么求的 $f_n$。

  一种比较显然的方法就是递推，我们显然可以从 $f_{n-2}$ 转移到 $f_n$：

$$f_n=(n-1)f_{n-2}$$

  然后就能 $O(n)$ 算出答案了。

链