E - Unbalanced ABC Substrings#

题目链接：https://atcoder.jp/contests/abc455/tasks/abc455_e

思路#

暴力做法#

首先考虑暴力做法，我们枚举每一个子串可能的左端点并扩展右端点，在过程中动态维护 $A,B,C$ 的出现次数，时间复杂度 $O(n^2)$

评测结果：https://atcoder.jp/contests/abc455/submissions/75267993

AC 15，TLE 21

Code#

1
// Problem: AT ABC455 E
2
// Contest: AtCoder - Ｓｋｙ Inc, Programming Contest 2026 (AtCoder Beginner Contest 455)
3
// URL: https://atcoder.jp/contests/abc455/tasks/abc455_e
4
// Time: 2026-04-25 20:00:07
5

6
#include <bits/stdc++.h>
7
using namespace std;
8

9
#define endl '\n'
10

11
typedef long long ll;
12
typedef unsigned long long ull;
13
typedef pair<int, int> pii;
14
typedef pair<double, double> pdd;
15

16
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
17
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
18
const int inf = 0x3f3f3f3f;
19
const int N = 0;
20

21
int n;
22
string s;
23
ll res;
24

25
bool check(int &a, int &b, int &c)
26
{
27
    return (a != b && b != c && a != c);
28
}
29

30
int main()
31
{
32
    cin >> n >> s;
33

34
    for (int i = 0; i < n; i++)
35
    {
36
        int a = 0, b = 0, c = 0;
37
        for (int j = i; j < n; j++)
38
        {
39
            if (s[j] == 'A')
40
                a++;
41
            if (s[j] == 'B')
42
                b++;
43
            if (s[j] == 'C')
44
                c++;
45

46
            if (check(a, b, c))
47
                res++;
48
        }
49
    }
50

51
    cout << res << endl;
52
    return 0;
53
}

正解#

我们发现正着算“出现次数互不相同的子串”比较困难，我们考虑统计这个集合的补集，也就是有多少个子串中，至少有两个字符的出现次数相同。

我们假设：

集合 $S_{AB}$ ：子串中 A 的数量 = B 的数量
集合 $S_{BC}$ ：子串中 B 的数量 = C 的数量
集合 $S_{CA}$ ：子串中 C 的数量 = A 的数量

则我们要求的答案为 $Ans = U - |S_{AB} \cup S_{BC} \cup S_{CA}|$

根据容斥原理，我们可以展开上述公式如下：

$|S_{AB} \cup S_{BC} \cup S_{CA}| = |S_{AB}| + |S_{BC}| + |S_{CA}| - |S_{AB} \cap S_{BC}| - |S_{BC} \cap S_{CA}| - |S_{CA} \cap S_{AB}| + |S_{AB} \cap S_{BC} \cap S_{CA}|$

这里有一个关键的逻辑：如果 A = B 且 B = C，那么自然有A = B = C，假设 $A,B,C$ 全相等的子串数有 $N_{ABC}$ 个，化简上述公式，可以得到 $Ans = Total - |S_{AB}| - |S_{BC}| - |S_{CA}| + 2 \cdot N_{ABC}$

如何快速求出 $|S_{AB}|$ （即 A 和 B 数量相等的子串）呢？我们可以使用前缀和的差值。

遍历字符串 $S$ ，记录到当前位置为止 A、B、C 的出现次数 $c_A, c_B, c_C$ 。

对于任意一个子串 $S[l \dots r]$ ，如果它里面 A 和 B 的数量相等，意味着：

$c_A[r] - c_A[l-1] = c_B[r] - c_B[l-1]$

移项可得：

$c_A[r] - c_B[r] = c_A[l-1] - c_B[l-1]$

结论：只要两个位置的前缀和差值 $(c_A - c_B)$ 相等，这两个位置之间的子串中 A 和 B 的数量就相等。

同理：

记录 $(c_B - c_C)$ 的频率来求 $|S_{BC}|$
记录 $(c_C - c_A)$ 的频率来求 $|S_{CA}|$
记录 $(c_A - c_B, c_B - c_C)$ 的频率来求 $N_{ABC}$

Code#

1
// Problem: AT ABC455 E
2
// Contest: AtCoder - Ｓｋｙ Inc, Programming Contest 2026 (AtCoder Beginner Contest 455)
3
// URL: https://atcoder.jp/contests/abc455/tasks/abc455_e
4
// Time: 2026-04-25 20:00:07
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14
typedef pair<long long, long long> pll;
15

16
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
17
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
18
const int inf = 0x3f3f3f3f;
19
const int N = 0;
20

21
int n;
22
string s;
23
ll res;
24

25
int main()
26
{
27
    cin >> n >> s;
28

29
    ll tot = 1LL * n * (n + 1) / 2;
30

31
    map<ll, ll> fab, fbc, fca;
32
    map<pll, ll> fabc;
33

34
    ll a = 0, b = 0, c = 0;
35

36
    fab[0] = 1;
37
    fbc[0] = 1;
38
    fca[0] = 1;
39
    fabc[{0, 0}] = 1;
40

41
    for (auto ch: s)
42
    {
43
        if (ch == 'A')
44
            a++;
45
        else if (ch == 'B')
46
            b++;
47
        else if (ch == 'C')
48
            c++;
49

50
        ll dab = a - b;
51
        ll dbc = b - c;
52
        ll dca = c - a;
53

54
        fab[dab]++;
55
        fbc[dbc]++;
56
        fca[dca]++;
57
        fabc[{dab, dbc}]++;
58
    }
59

60
    ll nab = 0, nbc = 0, nca = 0, nabc = 0;
61

62
    for (auto const &[k, v]: fab)
63
        nab += v * (v - 1) / 2;
64
    for (auto const &[k, v]: fbc)
65
        nbc += v * (v - 1) / 2;
66
    for (auto const &[k, v]: fca)
67
        nca += v * (v - 1) / 2;
68
    for (auto const &[k, v]: fabc)
69
        nabc += v * (v - 1) / 2;
70

71
    res = tot - nab - nbc - nca + 2 * nabc;
72

73
    cout << res << endl;
74
    return 0;
75
}