琪露诺的选择题

CSP_Sept · 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;
}