暴力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。