FEB

题意

给定一个长度为 $N$ 的字符串，只包含 B、E、F。

B 表示这条消息由 Bessie 发出。
E 表示这条消息由 Elsie 发出。
F 表示发送者被隐藏，可能是 B，也可能是 E。

把所有 F 替换成 B 或 E 后，定义兴奋值为相邻两条消息由同一头牛发送的次数，也就是 BB 或 EE 的出现次数。

要求输出所有可能的不同兴奋值，按从小到大排列。

思路

先看一个小数据暴力：

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/**
 * 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:26
 * update_at: 2026-07-11 16:28
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n;
string s;
string cur;
bool can_score[MAXN];

int calc_score() {
    int score = 0;
    for (int i = 0; i + 1 < n; i++) {
        if (cur[i] == cur[i + 1]) {
            score++;
        }
    }
    return score;
}

void dfs_fill(int pos) {
    if (pos == n) {
        int score = calc_score();
        can_score[score] = true;
        return;
    }

    if (s[pos] != 'F') {
        cur[pos] = s[pos];
        dfs_fill(pos + 1);
        return;
    }

    // 小数据暴力：每个 F 分别枚举成 B 或 E。
    cur[pos] = 'B';
    dfs_fill(pos + 1);
    cur[pos] = 'E';
    dfs_fill(pos + 1);
}

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

    cin >> n;
    cin >> s;

    cur = s;
    dfs_fill(0);

    int cnt = 0;
    for (int i = 0; i <= n - 1; i++) {
        if (can_score[i]) cnt++;
    }

    cout << cnt << '\n';
    for (int i = 0; i <= n - 1; i++) {
        if (can_score[i]) {
            cout << i << '\n';
        }
    }

    return 0;
}

暴力把每个 F 都枚举成 B 或 E，再统计相邻相同对。它的复杂度和 F 的数量指数相关，只能用于小数据验证。

满分做法不需要枚举每一种字符串。我们只要求所有可能的兴奋值，可以先求：

min_score：最小可能兴奋值。
max_score：最大可能兴奋值。
step：可达值之间的间隔，可能是 1 或 2。

没有 F 的相邻已知字符

如果相邻两个字符都不是 F，那么这条边已经确定：

相同：min_score 和 max_score 都加 1。
不同：都不加。

内部 F 段

考虑一段连续 F，左右两端都有已知字符：

text

1L F F ... F R

设这段里有 len 个 F，那么这里一共有 len + 1 条相邻边。

为了最大化兴奋值：

如果 $L == R$ ，可以全部填成同一个字符，贡献 len + 1。
如果 $L != R$ ，至少有一次变化，最大贡献 len。

为了最小化兴奋值，要尽量交替填写。是否能做到贡献为 0，取决于边数奇偶和左右端点是否不同：

text

1
2边数奇偶 == (L != R) 时，最小贡献为 0
否则最小贡献为 1

内部 F 段的可达贡献会隔 2 变化，因为每多制造一对相邻相同，通常要减少一对变化。

贴边 F 段

如果连续 F 段在字符串开头或结尾：

text

1
2F F ... F R
L F F ... F

它有一个自由端，可以让贡献从 0 到这段边数之间的每个整数都可达。因此只要首尾有 F，整体可达兴奋值就会变成连续区间， $step = 1$ 。

否则所有变化都来自内部 F 段，最终只会隔 2 取值， $step = 2$ 。

最后从 min_score 开始，每次加 step，一直输出到 max_score。

代码

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
84
85
86/**
 * 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:26
 * update_at: 2026-07-11 16:28
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n;
string s;
int possible_values[MAXN];
int possible_cnt;

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

    cin >> n;
    cin >> s;

    int min_score = 0;
    int max_score = 0;
    bool edge_free = (s[0] == 'F' || s[n - 1] == 'F');

    for (int i = 0; i + 1 < n; i++) {
        if (s[i] != 'F' && s[i + 1] != 'F' && s[i] == s[i + 1]) {
            min_score++;
            max_score++;
        }
    }

    int i = 0;
    while (i < n) {
        if (s[i] != 'F') {
            i++;
            continue;
        }

        int l = i;
        while (i < n && s[i] == 'F') {
            i++;
        }
        int r = i - 1;
        int len = r - l + 1;

        bool has_left = (l > 0);
        bool has_right = (r + 1 < n);

        if (has_left && has_right) {
            int edge_cnt = len + 1;
            int need_odd_change = (s[l - 1] != s[r + 1]);

            // 最大值：两端相同可全相同，两端不同至少有一次变化。
            max_score += edge_cnt - need_odd_change;

            // 最小值：尽量交替；若边数奇偶不匹配，就必须留下一个相等相邻对。
            if (edge_cnt % 2 != need_odd_change) {
                min_score++;
            }
        } else {
            // 贴边的 F 段有一个自由端，可以让相等对数量从 0 到边数任意变化。
            int edge_cnt = len;
            if (!has_left && !has_right) {
                edge_cnt = len - 1;
            }
            max_score += edge_cnt;
        }
    }

    int step = edge_free ? 1 : 2;
    possible_cnt = 0;
    for (int x = min_score; x <= max_score; x += step) {
        possible_values[++possible_cnt] = x;
    }

    cout << possible_cnt << '\n';
    for (int i = 1; i <= possible_cnt; i++) {
        cout << possible_values[i] << '\n';
    }

    return 0;
}

复杂度

扫描字符串和连续 F 段都是线性的。

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

总结

本题不要枚举每个 F 的具体取值，而是按连续 F 段统计它对兴奋值范围的影响。

内部段只会改变奇偶，贴边段能打破奇偶限制，让整个区间都可达。

目录

题意

思路

没有 F 的相邻已知字符

内部 F 段

贴边 F 段

代码

复杂度

总结