Lonely Photo

题意

给定一个只包含 G 和 H 的字符串，表示一排牛的品种。

一张照片对应一个长度至少为 3 的连续子串。如果这张照片里恰好只有一头 G，或者恰好只有一头 H，那么这张照片就是孤独的照片。

要求统计孤独照片的数量。

思路

先看一个最直接的暴力：枚举所有连续子串，统计其中 G 和 H 的数量。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 18:04
 * update_at: 2026-07-11 18:05
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;
char s[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }

    long long ans = 0;

    // 枚举所有长度至少为 3 的连续照片。
    for (int l = 1; l <= n; l++) {
        int cnt_g = 0;
        int cnt_h = 0;
        for (int r = l; r <= n; r++) {
            if (s[r] == 'G') {
                cnt_g++;
            } else {
                cnt_h++;
            }

            if (r - l + 1 >= 3 && (cnt_g == 1 || cnt_h == 1)) {
                ans++;
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

这个暴力的思路很直接，但子串数量是 $O(N^2)$ ，满分数据中 $N$ 可达 $5 \times 10^5$ ，不能这样做。

换一个角度：每张孤独照片中，只有一头牛是少数派。于是我们可以枚举这头“孤独的牛”是哪一头，并统计它能贡献多少张照片。

设当前枚举的位置是 i：

left：从 i 左边开始，连续多少头牛与 s[i] 不同；
right：从 i 右边开始，连续多少头牛与 s[i] 不同。

如果照片里 s[i] 是唯一的少数派，那么照片只能从这些连续异色牛中向左、向右扩展，不能越过同色牛。

贡献分三类：

左右两边都选：有 $left * right$ 种。
只选左边：至少要选 2 头异色牛，贡献 max(left - 1, 0)。
只选右边：至少要选 2 头异色牛，贡献 max(right - 1, 0)。

所以位置 i 的贡献是：

left \times right + \max(left - 1, 0) + \max(right - 1, 0)

每张孤独照片都有且只有一头少数派牛，因此按少数派位置统计不会重复，也不会漏掉。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 18:04
 * update_at: 2026-07-11 18:05
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 500005;

int n;
char s[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }

    ll ans = 0;

    for (int i = 1; i <= n; i++) {
        ll left_cnt = 0;
        ll right_cnt = 0;

        // 向左数连续的异色牛。
        int p = i - 1;
        while (p >= 1 && s[p] != s[i]) {
            left_cnt++;
            p--;
        }

        // 向右数连续的异色牛。
        p = i + 1;
        while (p <= n && s[p] != s[i]) {
            right_cnt++;
            p++;
        }

        // 当前牛作为唯一的少数派：左右各取一段，或者只在一侧取至少两头异色牛。
        ans += left_cnt * right_cnt;
        if (left_cnt >= 2) {
            ans += left_cnt - 1;
        }
        if (right_cnt >= 2) {
            ans += right_cnt - 1;
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

每个连续同色段只会在相邻边界附近被统计到，整体是线性扫描。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的关键是从“枚举照片”改成“枚举唯一少数派牛”。

这样每个位置只需要知道左右连续异色段长度，就能直接算出它对答案的贡献。

目录

题意

思路

代码

复杂度

总结