P4338:[ZJOI2018]历史 – 题解

主要思路

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 操作来进行判断和修改。我们需要判断是否存在虚子树中的点成为重儿子,然后进行切换。

继续阅读P4338:[ZJOI2018]历史 – 题解

P4501:[ZJOI2018]胖 – 题解

主要思路

可以比较显然的看出来是个区间扩展问题,单调的向两边进行扩展。

正常暴力可以考虑 \(n^2\) 进行扩展,然而这题显然有单调性,所以我们可以试着进行二分优化掉一个 \(n\)。二分出一个范围,然后再用 ST 表或者是线段树之类的东西去查一下区域内的最远距离然后就可以进行判断了。

代码有点长而且还有点复杂。

继续阅读P4501:[ZJOI2018]胖 – 题解