首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。