[ARC113E] Rvom and Rsrev

Genius_Star · 2026-04-02 16:18:00 · 题解

狗屎题，场上只差最后一步了/fn

思路：

看到题以及样例，你发现答案形式比较明显，于是考虑分讨。

首先你可以选择对最后一个 b 前面的相邻两个 a 进行操作，得到答案的一个下界 b\cdots ba\cdots a 或者 b \cdots b 或者 b \cdots bab \cdots ba \cdots a。

对于第三种情况，容易想到选择中间夹杂的那个 a 以及最后一个 b 后面的 a 进行操作，可以消掉第一个 a 使得答案更优。

这只是答案的一个下界，一定是 b \cdots b a \cdots a 的形式，考虑什么时候我们会更优？

• 因为上面操作中我们没有删 b，于是现在删 b 一定不优，所以答案一定是在所有 b 后面添加尽可能多的 a；怎么操作才可能多 a？考虑前面中一段很长的全 a 连续段 \cdots baa\cdots aab\cdots b a \cdots ，于是可以选择这个连续段的开头和 b 后面的那个 a 作操作，然后这个连续段就被翻转都后面了，但是此时会消耗掉两个 a，于是只有长度 \ge 2 的连续段翻转过去才会造成贡献。

• 经过上面的翻转后，再分讨一下，如果最后一个 b 前面还有偶数个单独的 a 还在，那么可以两两配对消除完，此时答案是最优的。

• 否则还有奇数个落单的 a 呢？两两配对中还剩下一个，那么可以选择 b 后面的第一个 a（即我们之前构造下界时的第三种情况）消除，此时也是最优的。

上面都是最后一个 b 后面有 a，然后用那个 a 一直和前面的再作操作；那如果 b 后面不存在 a 时怎么办？即 s_n = b 时：

• 考虑样例 2，你发现 babbb 时操作前后两个 b 后是 bba 比原串更优；推广一下，若最后一个 a 后面还有至少 3 个 b 时，那么选择最后一个 b 和前面任何一个下一位是 a 的 b 后消除翻转一定更优，此时会把前面选择 b 后面的 a 连续段翻到后面，那么显然一定翻连续段最长的那个。

• 此时就转化为了 b 后面有 a 的情况，找前面的 a 连续段再往后尽可能翻转即可。

• 否则后面没有至少 3 个 b，那么删 b 一定不优，将前面 a 两两配对后保留最后面那个即可。

时间复杂度为 O(n)。

场上思路有点乱，代码有些混乱，见谅。

完整代码：

 #include<bits/stdc++.h>
#define lowbit(x) x & (-x)
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define ctz(x) __builtin_ctz(x)
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e5 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int T, n;
char s[N];
inline void solve(){
    scanf("%s", s + 1);
    n = strlen(s + 1);
    int ca = 0, cb = 0;
    bool fa = 1, fb = 1, to = 0;
    for(int i = 1; i <= n; ++i){
        if(to)
          fa &= (s[i] == 'a');
        else{
            if(s[i] == 'a')
              to = 1;
            else
              fb &= (s[i] == 'b');
        }
        ca += (s[i] == 'a');
        cb += (s[i] == 'b');
    }
    // cerr << ca << ' ' << cb << '\n';
    if(fa && fb){
        printf("%s\n", s + 1);
        return ;
    }
    int endb = 0;
    for(int i = n; i >= 1; --i){
        if(s[i] == 'b'){
            endb = i;
            break;
        }
    }
    int prea = 0, w = n - endb, now = 0, sum = 0;
    for(int i = 1; i <= endb; ++i){
        if(s[i] == 'b'){
            if(now > 1 && w)
              w = w - 1 + now - 1;
            else if(now == 1)
              ++sum;
            now = 0;
        }
        else
          ++now, prea = i;
        // cerr << i << ' ' << now << '\n';
    }
    // cerr << '\n';
    if(!w)
      sum = ca;
    if(sum & 1){
        if(endb != n){
            for(int i = 1; i <= endb; ++i)
            if(s[i] == 'b')
                putchar('b');
            --w;
            while(w--)
              putchar('a');
            putchar('\n');            
        }
        else{
            int enda = 0;
            for(int i = n; i >= 1; --i){
                if(s[i] == 'a'){
                    enda = i;
                    break;
                }
            }
            if(prea + 3 <= n && prea > 1){
                // babbb
                // bba
                // cout << "Yes\n";
                int mx = 0, na = 0;
                bool flag = 0;
                for(int i = 1; i <= n; ++i){
                    if(s[i] == 'b'){
                        if(!flag)
                          na = now;
                        if(flag)
                          mx = max(now, mx);
                        now = 0;
                        flag = 1;
                    }
                    else
                      ++now;
                }
                int w = mx, _mx = mx, sum = 0;
                for(int i = 1; i <= n; ++i){
                    if(s[i] == 'b'){
                        if(now == _mx)
                          _mx = 0;
                        else{
                            if(now > 1 && w){
                                if(now == _mx)
                                  _mx = 0;
                                else
                                  w = w - 1 + now - 1;
                            }
                            if(!w)
                              sum += now;
                            else if(now == 1)
                              ++sum;
                        }
                        now = 0;
                    }
                    else
                      ++now;
                }
                if((sum & 1) && !mx)
                  putchar('a');
                for(int i = 1; i <= cb - (mx > 0 ? 2 : 0); ++i)
                  putchar('b');
                for(int i = 1; i <= w - (sum & 1); ++i)
                  putchar('a');
                putchar('\n');
            }
            else{
                for(int i = 1; i <= n; ++i){
                    if(s[i] == 'a' && i == enda)
                      putchar('a');
                    else if(s[i] == 'b')
                      putchar('b');
                }
                while(w--)
                  putchar('a');
                putchar('\n');    
            }
        }
    }
    else{
        for(int i = 1; i <= endb; ++i)
          if(s[i] == 'b')
            putchar('b');
        while(w--)
          putchar('a');
        putchar('\n');
        return ;
    }
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}