FEB (USACO Bronze 2023 US Open)

直接穷举所有的可能性是没有希望的，所以我们希望找到一个 $\mathcal{O}(N)$ 的一遍扫描就解决问题的办法。

首先通过观察一些局部的模式来找规律，最简单的模式是BB或者EE，各自会贡献一个“兴奋程度”，那么三个B或者E就会贡献2个“兴奋程度”。继续这个过程，我们还可以找到以下的包含F的模式:

BFB, EFE: 0, 2
BFE, EFB: 1
BFFB, EFFE: 1, 3
BFFE, EFFB: 0, 2
BFFFB, EFFFE: 0, 2, 4
BFFFE, EFFFB: 1, 3
...

稍微做一些总结，我们的规律就是:

$i$ 个B或者 $i$ 个E：贡献 $i-1$
开头结尾同样的B/E，中间奇数 $i$ 个F，或者开头结尾一个B一个E，中间偶数 $j$ 个F，贡献 $0, 2, ..., i+1$ 或 $j$ 。
开头结尾同样的B/E，中间偶数 $i$ 个F，或者开头结尾一个B一个E，中间奇数 $j$ 个F，贡献 $1, 3, ..., i+1$ 或 $j$ 。
S开头或结尾的 $i$ 个F: $0, 1, ..., i$
全部都是F: $0, 1, ..., n-1$

我们要求的答案就是这些可能的值全部加起来的所有可能结果，用笨办法枚举会导致复杂度过高，但是如果我们手工算几个数，就会发现只要算出结果的最小值、最大值，中间能取到的值的分布是有规律的。具体来说，我们从左到右扫描一遍，利用上面的规律就可以计算出来结果对应的最小值和最大值，这样就决定了取值的范围。而具体所有的可实际取到的值只有两种情况：

如果有开头和或结尾的F，那么取值就可以是最大值、最小值以及之间的所有数。
如果没有开头和结尾的F，那么取值就只能是最大值、最小值以及中间间隔为2的所有数。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;
char s[200005];
 
int main() {
    scanf("%d", &n);
    scanf("%s", s);
 
    int ans_max = 0, ans_min = 0;
    bool leading_ending = false;
 
    int i = 0;
    while (i < n) {
        int cnt = 1;
        while (s[i] == s[i+cnt])            // count repeats
            cnt++;
        if (s[i] == 'B' || s[i] == 'E') { 
            if (cnt > 1) {
                ans_max += cnt-1;
                ans_min += cnt-1;
            }
        } else {    // F
            if (i == 0 || i+cnt == n) {
                if (i == 0 && i+cnt == n)
                    ans_max += cnt-1;
                else
                    ans_max += cnt;
                leading_ending = true;
            } else {
                bool same = s[i-1] == s[i+cnt];
                bool even = cnt % 2 == 0;
                if (same && !even || !same && even) {   // contribute 0, 2, 4, ...
                    ans_max += even ? cnt : cnt+1;
                } else {                                // contribute 1, 3, 5, ...
                    ans_max += even ? cnt+1 : cnt;
                    ans_min += 1;
                }
            }
        }
        i+=cnt;
    }
 
    if (leading_ending) {
        printf("%d\n", ans_max-ans_min+1);
        for (int i = ans_min; i <= ans_max; i++)
            printf("%d\n", i);
    } else {
        printf("%d\n", (ans_max-ans_min)/2+1);
        for (int i = ans_min; i <= ans_max; i+=2)
            printf("%d\n", i);
    }
 
    return 0;
}