题解：CF2069E A, B, AB and BA
chenxi2009
·
·
题解
思路
此时若 `A` 的数量 $cnt_a>a$，或 `B` 的数量 $cnt_b>b$，我们就需要合并相邻的 `A`、`B`，构成 `AB` 或 `BA`。这两种新子串都可以减少一个 `A` 和一个 `B`，所以它们的数量总和至少得是 $\max(cnt_a-a,cnt_b-b)$。接下来考虑怎么尽可能多地合并出 `AB` 和 `BA`。
我们用连续的 `A` 和连续的 `B` 为分界（因为它们不能参与合并），可以把 $s$ 划分成几个内部合并会互相影响的子串。有如下形式：`ABABAB...ABA`、`BABABA...BAB`、`ABAB...AB`、`BABAB...A`。
令子串长度为 $l$，发现前两种是可以划分出 $\left\lfloor\frac{l}{2}\right\rfloor$ 个 `AB` 或 `BA` 的（暂不考虑 `AB` 或 `BA` 数量超限的情况）；\
第三种可以划分成 $\frac{l}{2}$ 个 `AB`，但是内部十分紧凑，如果要划分出 `BA` 的话只能划分出 $\frac{l}{2}-1$ 个 `AB` 或 `BA`；\
第四种和第三种类似，可以划分成 $\frac{l}{2}$ 个 `BA`，或 $\frac{l}{2}-1$ 个 `AB` 或 `BA`。
考虑贪心，前两者怎么用都没有损失，先保留，考虑后两者；第三种肯定优先拆 `AB` 直至数量达到 $ab$，由于**每有一个子串被分出了 `BA` 就会出现 $1$ 的损失**，我们优先让短的子串被拆成 `AB`，这样在限制 `AB` 的数量时，可以让更多的子串被**纯净地**拆分，损失更小。\
同理第四种子串也优先拿出短的拆成 `BA`，剩下的没拆完的子串才考虑 `AB`。
我们前面留下的前两种子串这个时候再来用。如果说最终拼出来的 `AB` 和 `BA` 的数量和 $\ge\max(cnt_a-a,cnt_b-b)$ 就是成功的，否则失败。
由于需要优先拿短的子串所以有一个排序过程，时间复杂度 $O(\sum\vert s\vert\log\vert s\vert)$。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int T,n,a,b,c,d,cnta,cntb,cnt,trn,l,tmp;
char s[600000];
vector<int>vc,vd;
int main(){
scanf("%d",&T);
while(T --){
scanf("%s%d%d%d%d",s + 1,&a,&b,&c,&d);
vc.clear(),vd.clear(),cnta = cntb = cnt = 0,l = 1,n = strlen(s + 1);
for(int i = 1;i <= n;i ++){
if(s[i] == 'A') cnta ++;//统计 A 和 B 的数量
else cntb ++;
}
trn = max(cnta - a,cntb - b);//我们需要这么多的 AB 或 BA
for(int i = 1;i <= n;i ++){
if(i == n || s[i] == s[i + 1]){
tmp = (i - l + 1) / 2;
if(tmp){
if(s[l] == s[i]) cnt += tmp;//前两种子串，可以任意分成 tmp 个 AB 或 BA
else if(s[l] == 'A') vc.push_back(tmp);//第三种子串，可以分成 tmp/2 个 AB 或 tmp/2-1 个 AB 或 BA
else vd.push_back(tmp);//第四种子串
}
l = i + 1;
}
}
sort(vc.begin(),vc.end());//排序，优先用小的
sort(vd.begin(),vd.end());
for(auto i : vc){
if(c < i) cnt += i - 1;//要超限了，可以分成 i-1 个 AB 或 BA
else trn -= i,c -= i;//不会超限，就组成 i 个 AB
}
for(auto i : vd){
if(d < i) trn -= d,i -= d,d = 0,cnt += i - 1;
else trn -= i,d -= i;
}
if(trn <= min(c + d,cnt)) printf("YES\n");//还有 cnt 个任意组成 AB 或 BA 的机会
else printf("NO\n");
}
return 0;
}
```