题解：AT_abc455_e [ABC455E] Unbalanced ABC Substrings

drac1 · 2026-04-28 11:24:01 · 题解

题目思路

我们的答案为：总字串数 - 不合法的字串数。

直接数“都不同”比较麻烦，所以我们反过来数“不合法”的子串：

• x = y。
• 或 x = z。
• 或 y = z。

我们使用前缀和思路。

• cntA[i] 表示前 i 个字符里 A 的个数。
• cntB[i] 表示前 i 个字符里 B 的个数。

要让他们相等就是 cntA[r] - cntB[r] = cntA[l] - cntB[l]。

所以只要两个前缀的 A-B 差值相同，这两个前缀之间的子串就满足 A 和 B 个数相等。

::::success[代码]

#include <bits/stdc++.h>
using namespace std;
void solve();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}
#define int long long
void solve() {
    int n;
    string s;
    cin >> n >> s;
    map<int, int> ab, ac, bc;
    map<pair<int, int>, int> cnt;
    int a = 0, b = 0, c = 0;
    int ans = 0;
    ab[0] = 1;
    ac[0] = 1;
    bc[0] = 1;
    cnt[{0, 0}] = 1;
    for (char t : s) {
        if (t == 'A') a++;
        if (t == 'B') b++;
        if (t == 'C') c++;
        int x = a - b;
        int y = a - c;
        int z = b - c;
        ans += ab[x];
        ans += ac[y];
        ans += bc[z];
        ans -= 2 * cnt[{x, y}];
        ab[x]++;
        ac[y]++;
        bc[z]++;
        cnt[{x, y}]++;
    }
    cout << n * (n + 1) / 2 - ans << '\n';
}

::::