自动搬运

查看原文

来自洛谷，原作者为

	Find_Yourself 竹杖芒鞋轻胜马，谁怕？一蓑烟雨任平生。

搬运于2025-08-24 22:16:22，当前版本为作者最后更新于2022-11-21 10:40:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

暴力1：直接 dfs 枚举每个位置状态，复杂度 $O(2^n)$，预计 10pts。

暴力2：考虑贪心，如果一个左括号有多个合法的右括号匹配，则一定选最靠右的，而一对括号匹配当且仅当字符相同且中间部分可以完全匹配。

怎么判断能否一段连续区间可以完全匹配呢？我们可以用栈模拟！

假设该区间为 $[l, r]$。如果栈在 $l-1$ 时的形态与 $r$ 时的形态相同，则可以匹配。

而栈的形态我们可以用字符串哈希记录。

所以我们只需要 $O(n)$ 预处理出每个位置的哈希值，然后对于每一个点，从右往左找第一个哈希值相等的位置，递归处理即可。复杂度 $O(n^2)$，预计 50pts。

正解：现在的瓶颈是如何 $O(1)$ 找到最靠右的匹配位置。

我们可以每个点的哈希值离散化并存入 vector 中进行分类。

然后对于当前状态 dfs(l, r)，二分坐标在 $[l, r]$ 范围中与 $l$ 匹配且最靠右的位置，即在 vec[hash[l]] 中进行 upper_bound。

最后复杂度均摊下来就是 $O(n\log n)$，预计 100pts。

code