自动搬运

查看原文

来自洛谷，原作者为

	CSP_Sept 私が戻ってきたのはね。 もう一度、星の音を聞くためだよ

搬运于2025-08-24 22:39:22，当前版本为作者最后更新于2022-08-07 17:20:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

琪露诺的选择题

考虑到我们可以先固定一定数量的 $\texttt A$，然后进行交换操作，这样省去了构造时的一个麻烦。

接下来注意到每次交换操作必定只会影响到偶数个答案的变更，单次交换只会让错误增加或减少 $2$ 个。

由于不想让减少占用讨论空间，发现初始固定状态下使错误数量最小即可让错误变化退化为仅增加。

于是先尽量使得固定状态下的错误数量最小，记为 $r$。将 $e$ 减去 $r$ 得到 $e'$，即为接下来需要产生的错误数量。

分别统计出 A,B 位置正确的数量，两者取 $\min$，即得到最大交换数量 $x$。

由上述讨论发现，当 $e'\equiv1\pmod2,e'>2x,e'<0$ 三者有一种成立即为无解。

有解的情况，交换 $\dfrac{e'}2$ 次正确的 $\texttt{A,B}$ 即可，在输出时稍加统计即可 $O(n)$ 做到。

#include <cstdio>
#include <algorithm>

#define N 200010
using namespace std;
int n, a, e;
char s[N];
int p[N];
void Solve(){
    scanf("%d%d%d", &n, &a, &e);
    int m = n << 1, b = m - a;
    int x = 0, y = 0;
    scanf("%s", s + 1);
    int r = 0;
    for(int i = 1 ; i <= m ; i++){
        if(s[i] == 'A'){
            if(a == 0)
                p[i] = 1, r++;
            else
                p[i] = 0, a--, x++;
        }
        if(s[i] == 'B'){
            if(b == 0)
                p[i] = 0, r++;
            else
                p[i] = 1, b--, y++;
        }
    }
    e -= r; int opx = min(x, y);
    int opa, opb;
    if(e < 0 || e & 1 || e > 2 * opx){
        puts("-1");
        return;
    }
    else opa = opb = (e >> 1);
    for(int i = 1 ; i <= m ; i++){
        if(p[i] + 'A' == s[i]){
            if(p[i] == 0){
                if(opa){printf("B"); opa--;}
                else printf("A");
            }
            else if(p[i] == 1){
                if(opb){printf("A"); opb--;}
                else printf("B");
            }
        }
        else printf("%c", p[i] + 'A');
    }
    puts("");
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--)
        Solve();
    return 0;
}