首页 > 代码库 > CodeForces 670E Correct Bracket Sequence Editor

CodeForces 670E Correct Bracket Sequence Editor

链表,模拟。

写一个双向链表模拟一下过程。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c=getchar(); x=0;    while(!isdigit(c)) c=getchar();    while(isdigit(c)) {x=x*10+c-0; c=getchar();}}const int maxn=500010;struct X{    bool f;    int nx,pr;}s[maxn];char t[maxn],op[maxn];int n,m,p;stack<int>S;int flag[maxn];int f1[maxn],f2[maxn];int main(){    scanf("%d%d%d",&n,&m,&p); p--;    scanf("%s",t); int len=strlen(t);    for(int i=0;t[i];i++)    {        if(S.empty()) S.push(i);        else        {            if(t[i]==() S.push(i);            else            {                if(t[S.top()]==()                {                    f1[S.top()]=i, f2[i]=S.top();                    S.pop();                }                else S.push(i);            }        }    }    for(int i=0;i<len;i++)    {        if(t[i]==() s[i].f=0; else s[i].f=1;        s[i].pr=s[i].nx=-1;        if(i!=0) s[i].pr=i-1; if(i!=len-1) s[i].nx=i+1;    }    scanf("%s",op);    for(int i=0;op[i];i++)    {        if(op[i]==L) p=s[p].pr;        else if(op[i]==R) p=s[p].nx;        else        {            int pos1=p,pos2;            if(s[p].f==0) pos2=f1[p]; else pos2=f2[p];            if(pos1>pos2) swap(pos1,pos2);           // for(int j=pos1;j<=pos2;j++) flag[j]=1;            flag[pos1]++;            flag[pos2+1]--;            if(s[pos1].pr!=-1) s[s[pos1].pr].nx=s[pos2].nx;            if(s[pos2].nx!=-1) s[s[pos2].nx].pr=s[pos1].pr;            if(s[pos2].nx!=-1) p=s[pos2].nx;            else p=s[pos1].pr;        }    }    LL sum=0;  //  for(int i=0;i<len;i++) printf("%d ",flag[i]);   // printf("\n");    for(int i=0;i<len;i++)    {        sum=sum+flag[i];        if(sum>0) continue;        printf("%c",t[i]);    }    printf("\n");    return 0;}

 

CodeForces 670E Correct Bracket Sequence Editor