题解 P6000 [CEOI2016]match

· · 题解

考虑用经典的字符串匹配问题判断是否无解。因为递归到最内层必定存在两个相邻的括号挨在一起，可以证明用栈做的正确性是对的。

考虑分治解决问题，即我们对于一个形如区间 [l,r] 的子问题找到能匹配到 l 的最远右端点，分别置为左右括号。

记 stk_i 表示在点 i 时栈的情况，不难发现如果两个点 l,r 能匹配在一起的充要条件是 s[l] = s[r] 且 stk_{l - 1} = stk_r。

判断栈是否相等等价于判断两个长度相等的字符串是否相等，用哈希就可以做了。

考虑要找最远端点，那么我们不妨直接维护一个二元组信息 (stk_i,hash_i) 的向右最远点并且对所有二元组信息相等的点连链表后每次暴力从最右边跑到第一个在区间内的答案。

不难证明这个做法的时间复杂度上限是 O(\frac{n ^ 2}{16}) 的，可在字符集大小为 1 是取到这个上界。

考虑一些更能摊的方法，不难发现字符串中每个位置只会和另一个位置匹配，所以这里的匹配量是 O(n) 的。

若采用 vector 把所有链表存下来可以获得一个上限 O(n \log^2 n)，思考更块的做法。

设 \phi[(stk_i,hash_i)] = |(stk_i,hash_i)| 表示一个二元组信息的势能函数，其初始值为所有具有该类二元组信息的位置的个数，若一共有 k 种二元组，不难发现 \sum_{i = 1} ^ k \phi_i = n。

若我们每次在递归解决问题时优先递归右区间并且将每层分治用到的二元组所对应的链表指针向前挪动，即按中-右-左的顺序遍历一棵区间拆分树可以保证后面遍历的区间使用到的信息一定不超过先前遍历的区间，即链表的指针不会向后挪回去。

那么我们可以得到所有链表的指针移动量为 O(n) 级别，算上 map 总的均摊时间复杂度就是 O(n \log n)。

如果精细实现的话可以去 map 做到 O(n)，不过想必也没人这么无聊。