2022-10-26

chenhx-xcpc / 2024-11-13 / 原文

被gtyz供的题创死了，但本质上还是菜...

》

T1 简单想一想就发现其实你不会跳超过 $\log_2$ 次，然后对每个节点维护每种权值对应的下一个元素是谁，可以用一个 last 数组来做，非常简单

》

T2 手玩样例发现其实答案只有四种取值 -1 / 0 / 1 / 2 ，其中 -1 是两个点不连通的情况，0 是同一个点，1 的话手玩一下发现是存在一条路径使得 $dist(x,y) \% 2=1$ ，否则就是 2 ，然后可以使用一个并查集来弄

》

T3 创死我了....，一个钟做完 T1T2 后把剩下的三个钟都用来整 T3 了，人麻了。首先先把怎么判赢弄出来，可以参考纳什博弈，然后就是只要存在某行之和为奇数即可，然后就会一个 $O(mn^2)$ 的做法，就是先前缀和之后哈希，然后就是数一数有多少的四元组 $(lx,rx,ly,ry)$ 使得 $s[lx][ly...ry]=s[rx][ly...ry]$ ，然后可以考虑维护哈希，接着就啥都想不到了，然后下午改题的时候 lsy 告诉我是 sam 模板3，人傻了

cp做法，就是如果你对很多个串排序之后，你的必然有 $lcp(s[i],s[i+k])=\min_{j=i}^{k-1}\{lcp(s[j],s[j+1])\}$

》

T4 看了一眼，迅速发现性质:

(1) T 是超现实树 $\rightarrow$ R(T) 是超现实树
(2) T 是超现实树 $\rightarrow$ cut(L(T))=L(R(T))

而且是充要的，就是直接考虑怎么生成一棵超现实树，然后就是假如你现在有一棵超现实树，然后你把左子树 T 抽出来，然后生成一棵 T' 使得 cut(T')=T ，然后问题就转化成了：

生成若干棵树 $\{T_N\}$ 使得 T[1] 是一个点，而对于 $\forall i\in[2,N]$ ，都有 cut(T[i])=T[i-1] ，然后这若干棵树的总叶子个数不超过 n ，总点数不超过 m ，最大深度不超过 k

直观的，考虑dp，设
f[a][b][c][d][e] 表示深度为 a ，上一棵树的总点数是 b ，叶子数是 c ，当前所有树的总点数是 d ，总叶子数是 e 的树的个数，转移显然

然后发现转移是 f[a][b][c][d][e] -(x>=c)-> f[a+1][b+x][x][d+b+x][e+x] 考虑优化，一开始的时候 f[1][0][0][1][1] 是有值的，别的都没值，然后你发现无论怎么转移 f[][x][][][y] 的 x,y 的差都是不变的，因为一开始只有 x=0,y=1 有值，所有在所有的后续转移出的状态中，一定都满足 b+1=e 然后你就成功的优化了状态，就是以后想优化 dp 的话还是要先把式子写出来之后观察式子来优化。

然后写一下题解做法，就是你发现实际上你从 T[1] 逐渐生成到 T[n] 这个 dp 的过程真的非常的困难，优化也难以实现(毕竟没见过)，然后其实不难发现，如果你一定确定 T[n] 了，然后你把中间的树们从 T[n] 一步步推出来是很简单的，所以说这个路径的个数本质上就是 T[n] 的个数，然后只需要 dp T[n] 即可