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 为了增加题目难度 / 防止被盒到原题而改的抽象题面。

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

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

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

没报上名 /yun。

1

先看的括号树。一开始直接把 ( 看作 $1$，) 看作 $-1$，然后求 $1$ 到 $i$ 的路径上区间和为 $0$ 的区间个数。

但是发现这是不对的，因为还要保证任意时刻前缀和 $\ge$ 起点的前缀和。

所以重新考虑。这里就不太好。

然后对于链可以进行括号匹配来统计，直接求出 $f_i$ 表示以 $i$ 为结尾的数量，然后做前缀和即可求出。

然后考虑转移到树上，其实还是可以看作一条链，只不过把别的链上的贡献去除掉即可。

2

然后开的纪念品。一开始考虑了一个暴力，但是发现读错题了，有多种物品，所以重新考虑。

手玩样例然后注意到了持续持有一个物品多天等价于我在下一天卖了然后再买入。

所以直接 dp 就行。

3

然后看的加工零件。因为是和相邻的有关，所以答案和奇偶性有关。

然后发现我要提供原材料首先我的距离必须 $\leq L$。其次就是这个点到询问点的距离的奇偶性必须和 $L$ 相同，所以跑一遍 bfs 预处理 $1$ 到其他所有点奇数长度的最短路，偶数长度的最短路然后判断即可。

4

开的 E 家的饭。首先形式化题意：有 $n \times m$ 的网格，每行至多选 $1$ 个，每列至多选 $\lfloor \frac{m}{2} \rfloor$ 个，然后不能不选，求方案数。

由于至多选的个数为 $\lfloor \frac{m}{2} \rfloor$，所以只能有一种物品不合法。那就考虑容斥。

直接考虑了一个暴力 dp，设 $f_{i,j,k}$ 表示前 $i$ 种方式，一共选了 $j$ 个，不合法的物品选了 $k$ 个的方案。

转移 $O(n^3)$ 的，做 $m$ 次，有 $84$ pts。

赛后看的题解，就是注意到我们只关心 $j,k$ 的相对大小，所以直接把 $j,k$ 放到一维里，维护差值 dp。时间复杂度 $O(n^2m)$