CSP-S2 2022 题解

发表于 2022-10-30 分类于题解阅读次数： Valine：本文字数： 356 阅读时长 ≈ 1 分钟

T1 作为一个 T1 还行吧。T3 没见过这个套路。T2 T4 都是垃圾。

T1 holiday

先把最短路都 bfs 出来，预处理一下从家出发到前两个不同点的可能性，然后考虑枚举中间的两点。

发现需要对于每个中间点求一下它的“半答案”的最大值、次大值和次次大值。

然后就做完了。

多写几个 ST 表就做完了，没啥好说的。

首先观察到一定能找到环这个性质没用，然后就发现你需要维护出度。

可以理解成每条存在的边的起始点是不重复的，且边数为 $n$ 。

然后你发现这个起始点是一个排列，因此你只需要判断是否为排列。

然后你使用随机赋权值 + hash 的做法通过了这道题。

$k = 1$ 直接做。

$k = 2$ 直接倍增维护在链上的 dp。

$k = 3$ 直接倍增维护在毛毛虫（以取 max 的形式当成链）上的 dp。