[AGC066C] Delete AAB or BAA

Genius_Star · 2026-09-03 19:49:09 · 题解

或许更好的阅读体验。

思路：

找性质题。

这种问题，考虑找极小可消除段，即对于一个能删空的段 [l, r]，定义它是极小的，当且仅当存在一种删除方式，使得它不能被分成 [l, mid], (mid, r] 两段，使得两段内可以单独删完。

那么对于一个消除完的区间 [l, r]，一定是由若干极小可消除段拼凑起来的，于是 dp 的时候就可以前面加一个极小可消除段而不是一个可删空的段这样比较难维护的信息。

考虑找到这个极小可消除段的充要条件，先找到一些必要的：

• 首先，要满足 A 的数量是 B 的两倍。

• 其次，由于是极小可消除段，那么最后一次删除一定是结合了开头结尾的，否则开头和结尾在两次被分别删了，一定可以分成两段分别删空；于是开头和结尾必须不同（相同的话 AAB, BAA 是消不掉的）。

显然，只要开头不等于结尾，且能删空，那么就是极小可消除段，于是只需要证明在这个基础上满足 A 的数量是 B 的两倍就可以把这个段删空，考虑归纳法：

• 当 n = 3，显然合法。

• 否则找到第一个长度 \ge 2 的连续 A 段，显然它左边或者右边至少有一个不是开头结尾的 B，否则会矛盾；于是可以删这个 AAB 或者 BBA 变成 n - 3 的子问题，由归纳得可以删空。

于是得证；那么令 B 为 -1，A 为 -2，此时前缀和是 S，那么 [l, r] 是极小可消除段只需要满足 s_l \ne s_r, S_r = S_{l - 1}，令 dp_r 表示考虑前 r 个字符最少可以剩多少个，那么两种转移：

• 找一个 l 满足 s_l \ne s_r, S_r = S_{l - 1}，有 dp_r \gets dp_{l - 1}。

容易开个桶维护满足条件的 dp 最小值，时间复杂度为 O(n)。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) (x) & (-(x))
#define popcnt(x) __builtin_popcount(x)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 4e6 + 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;
int a[N], dp[N], mn[N][2];
char s[N];
inline void solve(){
    scanf("%s", s + 1);
    n = strlen(s + 1);
    a[0] = 0;
    for(int i = 1; i <= n; ++i)
      a[i] = a[i - 1] + (s[i] == 'A' ? 1 : -2);
    for(int i = 0; i <= n; ++i)
      a[i] += (n << 1);
    for(int i = 0; i <= (3 * n); ++i)
      mn[i][0] = mn[i][1] = 1e9;
    dp[0] = 0;
    mn[a[0]][s[1] - 'A'] = 0;
    for(int i = 1; i <= n; ++i){
        dp[i] = dp[i - 1] + 1;
        dp[i] = min(dp[i], mn[a[i]][(s[i] - 'A') ^ 1]);
        mn[a[i]][s[i + 1] - 'A'] = min(mn[a[i]][s[i + 1] - 'A'], dp[i]);
        // cerr << dp[i] << ' ';
    }
    // cerr << '\n';
    write((n - dp[n]) / 3);
    putchar('\n');
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}