CF670E Correct Bracket Sequence Editor

思路

发现此题除了模拟没有好的方法，所以考虑如何模拟。

先考虑删除操作，如果在删除的时候再去找要删除那些的话，就会使时间复杂度变高，所以考虑先预处理出每个括号对应的位置。如果按照操作删除括号，那么时间复杂度也是非常吓人的。所以我们考虑标记被删除的括号。

再考虑移动操作，如果移动的下一个位置是被删除的操作，则跳转至下一个位置对应的括号的下一个位置，直到得到的位置没有被删除。

最后再关注一下删除后光标的移动方式，模拟就写完了

TLE code

#include<bits/stdc++.h>
using namespace std;
int n,m,p,tz[500005],z[500005],top;
bool vis[500005];
char s[500005],t[500005];
int main()
{
	scanf("%d%d%d%s%s",&n,&m,&p,s,t),--p;
	for(int i=0;i<n;++i)
		if(s[i]=='(') z[++top]=i;
		else tz[i]=z[top],tz[z[top--]]=i;
	for(int i=0;i<m;++i)
	{
		if(t[i]=='L')
		{
			--p;
			while(vis[p]) p=tz[p-1]-1;
		}
		if(t[i]=='R')
		{
			++p;
			while(vis[p]) p=tz[p+1]+1;
		}
		if(t[i]=='D')
		{
			vis[p]=vis[tz[p]]=1,p=max(p,tz[p]);
			int tp=p;
			if(p==n-1) while(vis[p]) p=tz[p]-1;
			else{++p;while(vis[p])p=tz[p]+1;}
			if(p==n){p=tp;while(vis[p]) p=tz[p]-1;}//如果左边没括号了，就跳转到左边第一个没删除的括号
		}
	}
	for(int i=0;i<n;++i)
	{
		if(vis[i]) i=tz[i];
		else printf("%c",s[i]);
	}
	return 0;
}

但是 TLE 了，怎么办？

先分析一下 TLE 的原因，如果在括号都是 () 且删除了一些括号的情况下，频繁地在被删除的括号左右移动，就非常容易超时。

所以考虑减少跳转的次数，想到了记录每个括号左右第一个没删除的位置，移动操作的时间复杂度就变成了 \(O(1)\)。

AC code

#include<bits/stdc++.h>
using namespace std;
int n,m,p,tp,z[500005],top;
char s[500005],t[500005];
struct node{int l,r,tz;}a[500005];
int main()
{
    scanf("%d%d%d%s%s",&n,&m,&p,s,t),--p;
    for(int i=0;i<n;i++)
	{
    	a[i].l=i-1,a[i].r=i+1;
    	if(s[i]=='(') z[++top]=i;
    	else a[i].tz=z[top],a[z[top--]].tz=i;
	}
	for(int i=0;i<m;i++)
	{
		if(t[i]=='L') p=a[p].l;
		if(t[i]=='R') p=a[p].r;
		if(t[i]=='D')
		{
			p=min(p,a[p].tz),tp=a[p].tz;
			if(a[p].l!=-1) a[a[p].l].r=a[tp].r;//注意边界
			a[a[tp].r].l=a[p].l;
			if(a[a[p].l].r==n) p=a[p].l;
			else p=a[tp].r;
		}
	}
	while(p>0&&a[p].l!=-1) p=a[p].l;
	while(p<n) printf("%c",s[p]),p=a[p].r;
    return 0;
}