AGC026E Synchronized Subsequence

首先分析性质

我们将配对的 $i,j$ 当成区间 $[i,j]$，容易发现区间一定没有包含，因为如果存在 $i \le x \le y \le j$， $i,j$ 配对，$x,y$ 配对是不合法的，应该为 $i,y$ 配对， $x,j$ 配对。

我们还可以发现对于每个连通块（这里联通块的定义为如果区间有交则连边后的连通块）如果 $i,j$ 配对，那么 $\forall (x,y) \in 配对的集合$（下文中这种二元组代表配对），有 $s_i=s_x,s_j=s_y$，证明方法和上面相同。

现在我们分开考虑每一段，求出每一段的答案在进行合并，那么可以分为两种情况：

1. 对于 $(i,j),s_i=a,s_j=b$

   首先答案肯定形如 $abab\cdots abab$，因为对于每一个前缀 a 的个数一定是大于等于 b 的个数的，所以这样最优，因为区间没有包含，所以我直接贪心的选最前的和已选集合不交的配对就好了。

2. 对于 $(i,j),s_i=b,s_j=a$

   结论：我肯定会删一个配对的前缀。

   证明：思考一下我们为什么要删去一个配对，因为这里面都是 b 在 a 前面，所以只有删掉之后 a 后面的 b 并过来了才会优，即肯定是这样的 bbabbaaa，所以你肯定是删掉一个前缀。

现在考虑怎么将答案合并，这个也很简单，我们用 stack 存下来现有答案，考虑加进来一个最优解之后怎么做，我们肯定是弹掉所有比他字典序小的，然后把他接到后面。

但是我们每一段一定是取字典序最大的吗，有没有可能是字典序小但是短的？

答案是不会的，因为首先如果字典序不是因为长度短，那么肯定是劣的，如果因为是长度段，首先发现第一种肯定是不会受到这个影响的。考虑第二种，长度长的比长度短的长出来的那一段一定是 a 的个数大于 b 的个数的，不然他就不可能在一段了，那么这样短串就不合法了，所以这是对的。

code:

const int N=6007;
int n;
string s;
int sum[N];
int ano[N];
bool flag[N];
string str[N];
string stk[N]; int id[N];  int top;
inline string solve(int l,int r){
	string ans="";
	if(s[l]=='a'){
		int now=l;
		while(now<=r){
			if(s[now]=='a') ans+="ab",now=ano[now]+1;
			else now++;
		}
	}
	else{
		int m=0;
		for(;;m++){
			int cnt=m; string now="";
			for(int i=l;i<=r;i++) flag[i]=0;
			for(int i=l;i<=r;i++){
				if(cnt&&s[i]=='b') flag[i]=flag[ano[i]]=1,cnt--;
				if(!flag[i]) now+=s[i];
			}
			if(cnt) break;
			str[m]=now;
		}
		ans=str[0];
		for(int i=1;i<m;i++) ans=(ans<str[i])?str[i]:ans;
	}
	return ans;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	#endif
	rd(n),n<<=1;
	cin>>s,s=" "+s;
	int pre=1;
	for(int i=1;i<=n;i++){
		if(s[i]=='b') continue;
		while(s[pre]!='b') pre++;
		ano[i]=pre,ano[pre++]=i;
	}
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(s[i]=='b'?1:-1);
	for(int l=1,r=1;r<=n;r++){
		if(sum[r]==0){
			string now=solve(l,r); l=r+1;
			while(top&&stk[top]+now<now) top--;
			stk[++top]=now,id[top]=++shu;
		}
	}
	for(int i=1;i<=top;i++) cout<<stk[i];
	puts("");
	return 0;
}