题解 CF1970A3 Balanced Unshuffle (Hard)

· · 题解

学长组在模拟赛里的题，赛时因为 50000 个 std::stack 爆零了，所以警示后人尽量少使用基于 std::deque 的容器。

看了下题解区另外的两篇题解，都写的比较长，这里讲一个实现简单的算法。

题意

参见题意翻译。

分析

因为这是一个合法的括号序列，所以 x 的左括号数量和 x+1 的右括号数量是相等的。

然后我们根据这个性质对变换出的结果进行分段，从左往右依次扫描统计 x 的左括号数量直到遇到右括号，接着将 x \gets x+1，继续扫描直到右括号数量抵消掉左括号数量即可。

因为第二关键字是按在原序列中的位置降序排序，所以对于字符存在对应 x 的栈中即可，最后模拟依次取出栈顶即可。

时间复杂度 O(n)。

代码

//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 500005
using namespace std;
int n;
char s[MAXN];
stack<char,vector<char> > t[MAXN];//注意使用 std::vector 特化的 std::stack，否则空间会超限。
int main(){
    scanf("%s",s),n=strlen(s);
    int x=0,l=0,r;
    for(int i=0,j;i<n;i=j){
        for(j=i;j<n&&s[j]=='(';j++)t[x].push(s[j]),++l;
        ++x;
        for(r=l,l=0;j<n&&r;j++) t[x].push(s[j]),s[j]=='('?++l:--r;//在抵消右括号数量的同时也要统计新的 x 的左括号数量。
    }
    x=0;
    for(char c;!t[x].empty();)
        putchar(c=t[x].top()),t[x].pop(),x+=c=='('?1:-1;//取出栈顶，然后计算新的 x。
    return 0;
}