T1

简单题，先排序，然后扫一遍二分求贡献，然后前缀后缀取个 $\max$ 枚举中间点就好。100 分

T2

首先转化题意：$d + kx = s$。

其中 $d$ 为横向移动距离，$k$ 为上下移动距离。

然后题意说要让 $x$ 最小，于是一开始写了个按 $k$ 为第一关键字的最短路。

但是我的答案小了，又注意到是最短路，于是写了个按 $d$ 为第一关键字的最短路，然后大小样例都过了。

但是我当时就非常疑惑，就感觉不大对劲。（事实证明我的感觉是对的，的确假了）。

只得了 51 分。正解是直接二分答案，然后跑最短路。可能是我对题意理解错了吧。

T3

首先考虑 $x$ 的取值是 $[1, n]$ 的，然后就可以枚举 $x$，然后如果有 $m$ 的话，可以枚举长为 $m$ 的这个串的开头，然后算贡献。

一开始卡在如何快速算贡献上了，但是很快想到多重集排列，于是 $n^3$ 就拿到了。

接着考虑实际上它每次是跳 $x$ 的，这个复杂度总共是 $O(n \ln n)$ 的，于是套上 hash 就有了一个 $O(n^2 \ln n)$ 的做法。有 50 分。

但是我写出来答案大了，我就猜是算重了，然后又注意到对于同一个 $x$ 如果删完之后两个字符串一样，那他们的贡献只能被算一遍。

好吧，啥都想到了但就是写挂了。

正解就差一步，还是读题问题。

题面中说了，所有长为 $x$ 的子串得连续，所以就不存在 $m$ 把一个 $x$ 分搁开的情况。

所以枚举 $m$ 的位置也是 $\frac{n}{x}$ 的。调和级数，然后就对了。

T4

首先 $n^2$ 好做，直接 $n$ 遍 dfs 即可。

接着考虑了特殊性质 $B$，一个菊花。

首先根可以找其他 $n - 1$ 个点。

其次考虑枚举非根，那么根据这个点和根的大小关系，可以得知这个点作为 $\min$ 还是 $\max$。

然后贡献就好算了：

• 作为 $\min$，此时 $rt > i$，那么另一个 $\max > rt$，所以贡献为：$n - rt$。

• 作为 $\max$，此时 $rt < i$，那么另一个 $\min < rt$，所以贡献为：$rt - 1$。

然后写代码的时候我是都算了两遍，最后除 $2$ 即可。35 分。

正解是考虑在最小、最大生成树的 Kruskal 重构树上做。

这个还没学，等学会了在补。

总结

最终 100 + 100 + 50 + 35 $\to$ 100 + 51 + 0 + 35。

我有理由怀疑 mx 为了增加题目难度 / 防止被盒到原题而改的抽象题面。

但确实自己水平还是不够，读题不够仔细。

所以还是练练读题，以及在烦躁的时候静下心来读题。

然后再拓展学学一些进阶算法。