[Codeforces Round #794 (Div. 2)] D. Linguistics

我是什么东西艹艹艹

《我离正解只差个sort》

首先，观察字符串，可以发现：若存在形似$AA……BB$或$BB……AA$等有两个相同的字符挨在一起的情况，则我们在它们中间放一块隔板

$BAABBABBAA\rightarrow$ $BA$ $AB$ $BAB$ $BA$ $A$

$ABABABBAABAB\rightarrow $ $ABABAB$ $BA$ $ABAB$

那么，位于同一区间的所有字符都是$AB$相间的形式，也就是说，可以用碎片$AB$和$BA$来拼凑出它们

当某一区间的字符个数为奇数时，如$ABA$，若想使用$AB$或$BA$，则一定会删去一个$A$，而具体是哪一个$A$，并不用关心（删去不同的$A$，则会导致用于表示这一区间的碎片不同，后文会具体提到）

称一个区间最理想的使用碎片的情况（即全用一种碎片拼凑出整个区间）为一个区间使用的碎片

当某一区间的字符个数为偶数时，如$ABABABABAB$，那么最理想的情况是用五个$AB$来凑这段区间，而当我们$AB$不够用的时候，设当前只有两个$AB$，则可以将原区间用$ABAB$，$A$，$BABA$，$B$拼凑出来

也就是说，当前区间为偶数时，可以通过使用一个$A$与$B$来使得区间使用的碎片发生变化

综上，可以发现，当区间为奇数时，它使用的碎片是不确定的，而当区间为偶数时，它使用的碎片是确定的（偶区间使用的碎片可以使用$A$与$B$来改变）

所以，我们先处理区间为偶数时的情况，因为这时使用的碎片确定

当有多个偶数区间使用的碎片都为$AB$时，举个例子：

$AB$ $AB$ $ABABABAB$ $ABABABABAB$

我们将这些区间按照大小从小到大排序，因为$AB$不一定能都填满所有的区间，所以我们从长度小的区间开始填，这样，我们就能保证被填满的区间最多，而没有填满的区间使用$A$和$B$来进行转换其使用的碎片，这样就能确保我们使用的$A$和$B$尽可能少

原因：对于我们仅有的$A$，$B$，它们可以用来更改区间使用的碎片以及填充区间，既其能够使用的情况与其作用是远远大于$AB$和$BA$的，所以我们希望$A$，$B$能够尽可能多的剩下

在我们解决完偶区间后，我们考虑奇区间

首先，若当前区间为$AB……BA$的形式，则用一个碎片$A$替代最前面或最后面的$A$（相当于删去最前面或最后面的$A$），这样就能使用$AB$或$BA$去填满这个区间

$ABABABABABA\rightarrow $ $A$ $BABABABABA$

而若我们剩下的$AB$或$BA$不能靠自己这一类去填满当前区间，也就是我们需要用$AB$和$BA$两种碎片给来拼凑同一区间，则我们将碎片$A$替代的字符变成区间中一个非端点的$A$，此时区间被划分成了两半，左边一半使用的碎片为$AB$，右边一半使用的碎片为$BA$

$ABABABABABA\rightarrow$ $ABAB$ $A$ $BABABA$

综上，对于奇区间，无论怎样用$AB$和$BA$拼凑，都只需要用一个$A$或$B$，所以我们只需要在偶区间操作完后再判断一下$A/B$的数量+$AB$的数量+$BA$的数量是否能填满奇区间即可

对于$A/B$：若我们先将奇区间中使用的单个A和B删去后，A和B的数量一定是相等的，因为它们在偶区间中的使用是成对出现的

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a,b,c,d,n,cnt1,cnt2,qk[N],tot;
int sum,sum1,sum2;
char s[N];
vector<int> t1,t2;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		cnt1=cnt2=tot=sum=sum1=sum2=0;
		t1.clear(),t2.clear();
		scanf("%d%d%d%d",&a,&b,&c,&d);
		getchar(); cin>>s+1;
		n=strlen(s+1);
		
		if(a+b+(c+d<<1)!=n){ printf("NO\n"); continue; }
		for(int i=1;i<=n;++i) if(s[i]=='A') ++cnt1; else ++cnt2;
		if(cnt1!=a+c+d||cnt2!=b+c+d){ printf("NO\n"); continue; }
		
		for(int i=2;i<=n;++i) if(s[i]==s[i-1]) qk[++tot]=i-1;
		qk[++tot]=n;
		
		for(int i=1;i<=tot;++i){
			int t=qk[i]-qk[i-1]>>1;
			if((qk[i]-qk[i-1])%2){
				if(s[qk[i]]=='A') --a;
				else --b;
				sum+=t;
			}else{
				if(s[qk[i]]=='A') sum2+=t,t2.push_back(t);
				else sum1+=t,t1.push_back(t);
			}
		}
		if(a<0||b<0||a!=b){ printf("NO\n"); continue; }
		sort(t1.begin(),t1.end()),sort(t2.begin(),t2.end());
		
		for(int i=0;i<t1.size();++i){
			if(c>=t1[i]) c-=t1[i];
			else{
				if(d+c+1>=t1[i]) d-=(t1[i]-c-1),--a,c=0;
				else a-=(t1[i]-c-d),d=0,c=0;
			}
			if(a<0||c<0||d<0) break; 
		}
		if(a<0||c<0||d<0){ printf("NO\n"); continue; }
		
		for(int i=0;i<t2.size();++i){
			if(d>=t2[i]) d-=t2[i];
			else{
				if(d+c+1>=t2[i]) c-=(t2[i]-d-1),--a,d=0;
				else a-=(t2[i]-d-c),d=0,c=0;
			}
			if(a<0||c<0||d<0) break;
		}
		if(a<0||c<0||d<0){ printf("NO\n"); continue; }
		
		if(a+c+d>=sum) printf("YES\n");
		else printf("NO\n");
	}


	return 0;
}