模拟赛全集
嘉然登场
挺不错的题，发现对于每个数，都有固定的数可以与其相邻，而且排序之后是整个序列的一段后缀
首先我们发现当序列有解的时候一定有数可以和任何一个数相邻，丢进去就完事了
那么我们考虑对于每个值，让能放到它旁边的值全扔进去，之后直接暴力插入任意一个缝隙就好了，注意到这样之后就没有能放到其旁边的数了，直接将其左右两边合并成一个位置就好了
容易发现这样之后会生成一个子问题，和之前没什么区别，接着上面的做就好了，这个可以维护当前缝隙数来做，左右两边指针相遇的时候就求出结果了
Clannad
也是不错的题，发现在线不好做，考虑离线下来做
考虑一个朴素做法，求出区间 lca 之后暴力跳到 lca，之后将经过的点打上标记 树剖加上 bitset \(O(\frac{n^2}{w})\) 即可通过此题
考虑将贡献拆开尽量变成每个下标独立贡献，发现就是每个值到根的链上的路径交长度减去 lca 的深度，后者可以直接用经典 trick 求
问题变成树链推平，查询颜色在 \(l\)，\(r\) 之间的节点个数，扫描线之后用后面的覆盖前面的，扫到询问末尾就更新答案，这里树链推平可以树剖之后珂朵莉树维护，至于查询颜色在 \(l\)，\(r\) 之间的节点个数，用个树状数组或者线段树就做完了
修水管
挺难的 dp 了，发现求水管修复概率比求期望要简单，考虑分别计算每段水管的概率
因为一轮只能修一个，而且要按照顺序，只需知道有多少轮能让 \(i\) 被判断就有办法计算，所以将 \(dp_{i,j}\) 设为前 \(i\) 条水管中有 \(j\) 条修复了的概率，发现可以如下转移
\[dp_{i,j}=dp_{i-1,j} \times (1-p_i)^{r-j} \]\[dp_{i,j}=dp_{i-1,j-1} \times (1-(1-p_i)^{r-j+1}) \]初始化 \(dp_{0,0}=1\) 即可递推出所有的状态结果，最后考虑计算答案，发现 \(P_i\) 就是通过第二个方程转移过来的所有数之和，也就是 \(P_i= \sum dp_{i-1,j-1}\times (1-(1-p_i)^{r-j+1})\) 直接暴力计算即可
最后 \(\sum w_i P_i\) 即所求
小孩召开法 3
多组询问 01 背包，猫树分治
首先暴力跑背包可以得到三十高分
考虑一个分块做法，将每块边界的背包前缀和，后缀和求出，之后合并，只计算答案为查询大小的值，容易发现单次合并复杂度是 \(O(T)\)，预处理 \(O(n\sqrt n T)\)，询问 \(O(m \sqrt n T)\)，上界在预处理和块内，莫队可以达到差不多的复杂度
发现复杂度不对的主要原因是不是每个区间都包含预处理边界，一个区间包含多个，处理块内太磨叽
直接改成分治就做完了
BB
为数不多切掉的有意义题目
考虑子树内有自己节点相当于自己给自己钱，所以每个节点权值变成 \(w_i+son_i-h_i\)，sort一遍就做完了
长途巴士
主页单开了一篇写
随
想你了Delov学长
发现p巨小无比，所以直接写每个数在答案中出现的概率
有式子 \(dp_{i \times j \mod p}=\sum dp_i \times p_j\)
容易发现这玩意是个多项式乘法 plus，就是把中间的加法做成乘法，直接倍增（快速幂）就做完了
串串
其实本来不大想写这题，后来看到大家基本都写的难绷哈希决定写一写
发现对于一个点，若以其为中心的最长回文串既不顶到开头，也不顶到结尾，那么一定不能是答案，如果顶到结尾就是答案，顶到开头的话将它翻转之后的末尾的答案和他一样
所以 manacher 求出以每个字符为中心最长奇回文子串就好了
桥桥
考虑不带修怎么做：显然是离线下来按照重量将询问和边权排序，把大于询问权的边全部插入，这样就不需要维护删边
对于本题，我们可以尝试使用类似的思路，发现因为有可撤销并查集，我们是可以删除后插入的部分边的
所以对询问分块，对于块内没改的边直接插入并查集，对于改过的边，暴力 \(O(\sqrt m)\) 扫一遍判断要不要加入就好了
使用归并排序和 Kaguya 学长教的可撤销路径压缩并查可以做到 \(O(m\sqrt {m \alpha(m)})\) 的优秀复杂度但是我实现太垃圾打不过若干带 \(\log\) 写法
春色春恋春熙风
发现其实是要求只有至多一个奇数出现次数字符的路径最大长度
考虑枚举这个奇数字符，之后对于每条路径，令 \(0\) 表示偶，\(1\) 表示奇，一条路径的状态就是其左右两部分异或起来
根据很多淀粉质题带来的启发，我们最好分别对每个节点都求出以这个节点为 lca 的最长合法路径，对于判断合法路径，由于 lca 到根的那段在两边到根的树链上，所以给每个节点赋上到树根路径上的状态作为权值即可
为了让复杂度正确，我们需要类似其他题，对每个状态开一个桶，之后拼合左右两边
这题和其他套路题不同的是这个桶的状态太多，所以复杂度会退化成 \(O(n^2w)\) （w 是字符集大小），我们发现复杂度主要卡在桶的合并上，这个是 \(O(n^2)\) 的时空复杂度，这时候采用线段树合并即可获得高贵的大常数 \(O(wn \log n)\) 做法，注意空间复杂度为 \(O(nw)\) 卡卡常就能在 CF 上过掉
但是我们还有更加优秀的做法，当处理每个结点时
- 递归处理轻儿子
- 暴力跑一遍轻儿子子树，清空当前桶
- 处理重儿子，不清空桶
- 处理轻儿子，直接合并
我们发现这让轻儿子会被遍历好多好多遍，但是我们可以证明其复杂度是正确的，根据树剖结论即可发现复杂度为小常数 \(O(wn \log n)\)，容易发现这时候空间复杂度是 \(O(2^w)\)，不过貌似使用 unordered_map 可以将空间搞到 \(O(n)\)，但是小常数的优势也就没了（其实手写哈希表应该能规避类似的问题）
所以学长为什么不放线段树合并过
雪色雪花雪余痕
转化第二个限制，发现是说这是一个凸壳，就是说 \(\delta a\) 单调递增
标签：发现,每个,复杂度,路径,模拟,全集,节点,dp From： https://www.cnblogs.com/hzoi-wang54321/p/18353511