主要思路
狗屎状压题。
看到度数不超过 \(10\) 就知道需要状压儿子的信息。考虑处理一个 neck 数组来表示子树内节点到当前子树根下面的节点编号,然后我们每一次往上跳的时候我们都可以对这个数组进行调整,然后 DP 的时候就会比较愉快了。
处理 \(m\) 个请求的时候,我们把对应的 neck 提取出来,然后做标记,按标号小的进行 DP。
Continue reading →狗屎状压题。
看到度数不超过 \(10\) 就知道需要状压儿子的信息。考虑处理一个 neck 数组来表示子树内节点到当前子树根下面的节点编号,然后我们每一次往上跳的时候我们都可以对这个数组进行调整,然后 DP 的时候就会比较愉快了。
处理 \(m\) 个请求的时候,我们把对应的 neck 提取出来,然后做标记,按标号小的进行 DP。
Continue reading →ZJOI 的题质量都好高啊!真的都是很棒的题。
其实这个覆盖的东西就相当于在 LCT 上进行 Access 时轻重链切换的次数。我们考虑静态的问题,对于点 \(u\) 来说,如果子树内有多个来自不同儿子子树内的子代节点,那么就需要进行合理的分配来把这个轻重链切换次数搞到最大。
转换一下就是两两不同颜色的点进行配对的最大值。设 \(S_0 = a_u, S_i = [\text{第 } i \text{个子树内的 access 次数之和}]\)。那么答案其实就是 \(\max\{ \sum_{i = 0}^m S_i – 1, 2(\sum_{i = 0}^m S_i – \max_{i \in [0, m]} S_i) \}\),前者是啥都不考虑,后者是连接到一个子节点。后者成为最大值的条件其实就是要成为重儿子。我们考虑维护这个东西。
发现其实我们用贪心的分配方案进行轻重链剖分时,复杂度也是对的。因为被贪心选择的那个子节点确实也是个重儿子,根据树链剖分那一套理论这个复杂度是成立的。
当我们进行修改时,我们就需要用 Access 操作来进行判断和修改。我们需要判断是否存在虚子树中的点成为重儿子,然后进行切换。
Continue reading →打个表发现合法的区间需要满足以下条件之一:
我们可以考虑维护不合法的区间,因为不合法的区间特征明显一点,只有这种:
我们可以考虑用线段树来维护这个信息。大概就是需要固定左右端点的选择,然后再用分治的方法处理跨两个子树的区间即可。
Continue reading →说实话这绝对是我做过最垃圾的一套 ARC 了,没有之一。
Continue reading →这题还是蛮有意思,有一些奇怪的细节。
首先,只考虑正串,我们就直接塞进 AC 自动机里做套路 DP 即可。考虑串在后半段的情况,发现其实你只要刻画好前半段后半段即可被自动刻画,所以我们做串的反串并把字符取反塞到正串的 AC 自动机里就可以让字符串出现在后半段。