PKUWC2024部分题解

cyfff · 2024-01-27 22:16:49 · 个人记录

D1T1

简单 game 题，发现答案是括号序列能否匹配，易证。

D1T2

场上想到正解但没过。

考虑从笛卡尔树的角度生成 f 序列的过程：每次将当前子树对应的区间的 f 值增加 size*(a_{now}-a_{fa_{now}})，然后对两个儿子的子树递归做这个过程。

这显然是区间 dp 的形式，反着考虑这个过程，即需要将两个儿子的 f 值减至相同，然后合并为当前的 f 值。

因为可以减去 size 的自然数倍，故我们只关心这段区间的 f 模 size 最大都能达到多少。

设 f_{i,j,k} 表示区间 [i,j] 内的 f 值模 size=k 时 f 最大达到多少，枚举分割点用 exgcd,lcm 之类的方式合并即可，O(n^5)。

D2T1

十分位 \ge 5 的直接四舍五入，=0 的不影响答案。

优先匹配 4，再做 2+3 的匹配，剩下简单分类讨论，O(输入)。

D2T3

看到这种题首先把时间轴拍成序列，离线扫求答案。

有一个显然的分块 O(n \sqrt{n \log n}) 做法，其实也不会被卡常。

当然可以使用单侧递归线段树每次 pushup 时二分出当前时间段的 pop 最远 pop 到哪里，O(n \log^2 n)。