Leaders

题意

有 N 头牛排成一行，每头牛是 G 或 H。

第 i 头牛写下的名单是连续区间 [i, E_i]。

每个品种恰好有一个 leader。一个 leader 必须满足下面两个条件之一：

它的名单包含本品种所有牛；
它的名单包含另一个品种的 leader。

求有多少对 (G leader, H leader) 可能成立。

思路

先看一个小数据暴力：

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
61
62
63
64
65
66
67
68
69
70
71
72
73/**
 * 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 16:55
 * update_at: 2026-07-11 17:03
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n;
char breed[MAXN];
int e[MAXN];

bool list_has(int from, int to) {
    return from <= to && to <= e[from];
}

bool covers_all_same_breed(int leader, char c) {
    for (int i = 1; i <= n; i++) {
        if (breed[i] == c && !list_has(leader, i)) {
            return false;
        }
    }
    return true;
}

bool can_be_leader(int leader, char c, int other_leader) {
    if (covers_all_same_breed(leader, c)) {
        return true;
    }
    return list_has(leader, other_leader);
}

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

    string s;
    cin >> n;
    cin >> s;

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

    int ans = 0;

    // 直接枚举 G leader 和 H leader，按题意逐一检查。
    for (int g = 1; g <= n; g++) {
        if (breed[g] != 'G') {
            continue;
        }
        for (int h = 1; h <= n; h++) {
            if (breed[h] != 'H') {
                continue;
            }
            if (can_be_leader(g, 'G', h) && can_be_leader(h, 'H', g)) {
                ans++;
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

这个暴力直接枚举 G leader 和 H leader，再按题意检查两头牛是否都满足 leader 条件。它很适合理解题意，但枚举 pair 再检查覆盖关系，最坏会到 $O(N^3)$ 。

满分做法的关键是：名单只能向右延伸。

如果两个 leader 都没有覆盖本品种所有牛，那么它们就必须互相出现在对方名单中。可是两个不同位置不可能互相在对方右侧，所以这是不可能的。

因此任意合法 pair 中，至少有一个 leader 必须覆盖本品种所有牛。

能覆盖本品种所有牛的 leader 又只能是本品种最靠前的牛。因为如果它前面还有同品种牛，它的名单从自己开始，无法包含前面的同品种牛。

所以我们只需要找到四个位置：

first_g、last_g：最早和最晚的 G；
first_h、last_h：最早和最晚的 H。

若 E[first_g] >= last_g，则 first_g 可以作为 G leader。此时另一个 H leader 如果不是 first_h，它就不能覆盖所有 H，只能靠名单包含 first_g，也就是满足：

text

1i <= first_g <= E[i]

对 H 做同样的对称处理。

最后要单独判断 (first_g, first_h) 这一对。因为它可能同时落入“最早 G 做 leader”和“最早 H 做 leader”两类，如果不单独处理就容易重复计数。

代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83/**
 * 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 16:55
 * update_at: 2026-07-11 17:03
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
char breed[MAXN];
int e[MAXN]; // e[i] 表示第 i 头牛名单的右端点

int first_g, first_h;
int last_g, last_h;

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

    string s;
    cin >> n;
    cin >> s;

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

    for (int i = 1; i <= n; i++) {
        if (breed[i] == 'G') {
            if (first_g == 0) {
                first_g = i;
            }
            last_g = i;
        } else {
            if (first_h == 0) {
                first_h = i;
            }
            last_h = i;
        }
    }

    bool first_g_all = (e[first_g] >= last_g);
    bool first_h_all = (e[first_h] >= last_h);

    int ans = 0;

    // 如果 G 的最早牛能覆盖所有 G，则它可以作为 G leader。
    // 此时 H leader 若不是最早 H，就只能靠名单覆盖这个 G leader。
    if (first_g_all) {
        for (int i = 1; i <= n; i++) {
            if (breed[i] == 'H' && i != first_h && i <= first_g && e[i] >= first_g) {
                ans++;
            }
        }
    }

    // 对称地处理 H 的最早牛作为 H leader 的情况。
    if (first_h_all) {
        for (int i = 1; i <= n; i++) {
            if (breed[i] == 'G' && i != first_g && i <= first_h && e[i] >= first_h) {
                ans++;
            }
        }
    }

    // 最早 G 和最早 H 组成的 pair 单独计算，避免在上面两类里重复计数。
    bool g_ok = first_g_all || (first_g <= first_h && e[first_g] >= first_h);
    bool h_ok = first_h_all || (first_h <= first_g && e[first_h] >= first_g);
    if (g_ok && h_ok) {
        ans++;
    }

    cout << ans << '\n';

    return 0;
}

复杂度

只需要扫描常数次数组。

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

总结

本题的突破点不是枚举技巧，而是方向性。

名单只能向右延伸，排除了两个 leader 互相包含的可能，于是合法 pair 一定围绕最早的 G 或最早的 H 展开。把这两个最早位置单独拿出来分类计数，就能线性完成。

目录

题意

思路

代码

复杂度

总结