@hzjoiineg 为什么是神？

思路

首先将 \(S\) 中 A 的数量不等于 \(a + c + d\) 的情况判掉。

然后将 \(S\) 划分为 ABAB... 和 BABA... 的若干段，对于长度为奇数的段构造方案只能是如下构成：A 开头为例）：AB 和 BA 共 \(\lfloor \frac{len}{2} \rfloor\) 个，再加一个 A。将 \(a\) 减一，并用记录每一个长度为奇数的段的 \(\lfloor \frac{len}{2} \rfloor\) 之和记为 \(cnt\)，最后判断剩下的 A,B,AB,BA 能否凑出 \(cnt\) 个 AB 或 BA 即可。

其次对于长度为偶数的构造，要么用 \(\frac{len}{2}\) 个 AB；要么用 AB 和 BA 共 \(\frac{len}{2} - 1\) 个，同时使用一个 A 和一个 B。贪心地，我们显然希望在此情况下尽可能地使用 AB，不够的再用 BA 补，再不够的用 A,B 补。因为使用 A,B 的限制明显弱于使用 AB,BA 的限制。