CF670E Correct Bracket Sequence Editor题解

尹昱钦 · 2021-06-01 00:36:21 · 题解

解题思路

首先可以用一个栈求出每个括号配对的括号的位置———— 遇到左括号进栈，遇到右括号一定与当前的栈顶配对。

用双向链表储存一下某一个括号左面第一个没删的和右面第一个没删的括号的位置，这样可以 O(1) 执行左移和右移操作，删除也用双向链表的基本操作 O(1) 进行即可。

注意事项：

若第一个点的 left 设置为-1，则删点过程中一定要加 if 判断，防止越界。

AC代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=500005;
int n,m,p;
string s,s2; 
stack<int> st;
struct node{
    int left,right,to;
}e[maxn];
int main()
{
    cin>>n>>m>>p>>s>>s2;
    p--;
    for(int i=0;i<n;i++){
        e[i].left=i-1;
        e[i].right=i+1;
        if(s[i]=='(') st.push(i);
        else{
            e[i].to=st.top();
            e[st.top()].to=i;
            st.pop();
        }
    }
    for(int i=0;i<m;i++){
        if(s2[i]=='L') p=e[p].left;
        else{
            if(s2[i]=='R') p=e[p].right;
            else{
                if(p>e[p].to) p=e[p].to;
                if(e[p].left!=-1) e[e[p].left].right=e[e[p].to].right;
                e[e[e[p].to].right].left=e[p].left;
                if(e[e[p].left].right==n) p=e[p].left;
                else p=e[e[p].to].right;
            }
        }
    }
    while(p>0&&e[p].left!=-1) p=e[p].left;
    while(p!=n){
        cout<<s[p];
        p=e[p].right;
    }
    return 0;
}