题解：CF718E Matvey's Birthday

· · 题解

Matvey's Birthday

题目链接。cnblogs。

Problem

给定一个仅包含 a~h 的字符串（八个字符）。

有一个 n 个结点的无向图，编号为 0 到 n−1。结点 i 与结点 j 间有边相连当且仅当 |i-j|=1 或 S_i=S_j。

求这个无向图的直径和有多少对点间的最短距离与直径相同。

数据范围：2 \le n \le 10^5。

Sol

不难发现，直径一定不会超过 15。因为我可以通过传送后走一步来切换字符。然后这个东西不是很好贪心，n 又特别小，不难想到 DP。

不妨定义 f_{i, j} 表示点 i 走到第 j 个颜色的最短距离。这个东西是很好处理的，用类似于 BFS 的东西即可得到。

现在讨论直径，由于直径是 \max\limits_{i, j \in [1, n] \cap \mathbb Z}\min(|i - j|, \min\limits_c f_{i, c} + f_{j, c} + 1)。经过我们的转化，时间复杂度由 \mathcal{O}(n^2) 变为了 \mathcal{O}(n^2)！。

里面的 \min 是很不好的，由于答案一定不会超过 15，可以把 |i - j| \le 15 的二元组 (i, j) 单独拉出来跑。然后现在就只需要求 \max\limits_{i, j \in [1, n] \cap \mathbb Z} \min\limits_c f_{i, c} + f_{j, c} + 1 了。这个东西乍一看并不好做，但是发现传送只对颜色有要求，所以对于 a_i 相同的点，f_{i, c} 至多只会有两个值，因为如果不行的话，一定可以传送一次到达。如果记 g_{i, j} 表示颜色 i 走到颜色 j 的最小距离（g 可以在求 f 时一起得到），则显然有 g_{a_i, j} \le f_{i,j} \le g_{a_i, j} + 1。里面的 \min 不好拆掉，于是考虑枚举 i 算 j 的答案。然后不妨令 h_{i, j} = g_{a_i, j} - f_{i, j}。然后由于 h 的值域很小，可以把后面一维压起来，变为 h_{i}。发现相同的 (a_i, h_i) 的答案，无论 c, j 是多少，答案一定是一样的。于是可以枚举 a_i, h_i, c, j 来进行统计。h_i 的值有 \mathcal{O}(2^c) 种，所以时间复杂度为 \mathcal{O}(nc^22^c)。空间 \mathcal{O}(nc + c2^c)，这是因为我需要知道之前 (a_i, h_i) 出现了多少次，这需要开一个桶。

Code

评测记录。