2024寒假每日一题全部题解传送门>>

刚开始做确实没有什么思路，通过把样例模拟了一遍之后，大体理解该怎么去做了。

首先位于首尾位置的$ F $，对答案的贡献只有$ 0 $（与后（前）一个位置字母不同）和$ 1 $（与后（前）一个字母相同），而不处于首尾位置的$ F $，对答案的贡献的有以下几种情况：
1. $ EFB $ 即$ F $左右两侧的字母不同，会发现$ F $对答案的贡献始终都是$ 1 $，那么这种情况不用考虑。
2. $ BFB $ 即$ F $左右两侧的字母相同，发现$ F $对答案的贡献有两种情况，一种就是与左右字母不同，那么此时贡献就是$ 0 $，否则贡献为$ 2 $。

可以发现当首尾不存在$ F $的时候，中间的$ F $对答案贡献不是$ 0 $就是$ 2 $, 那么对于每个$ F $贡献的情况进行排列组合，最终可能的结果是以$ 2 $为公差的等差数列。如果首尾存在$ F $，那么对答案的贡献就可能多个$ 1 $，那么此时最终可能的结果就是以$ 1 $为公差的等差数列。分析完了之后，那么就要去贪心出这个数列的首项和末项（即答案可能的最小值和最大值）。

那么该如何去贪心出最小值和最大值呢？

来看个例子：$ FFFFBFFEFBFFFFF $
1. 首先来分析一下$ F $的前后缀$ FFFFB $ 和 $ BFFFFF的最值 $。求最小值的思路是尽可能的让相邻的两个字母不相同，这时候发现不管字母$ B $前（后）面的$ F $有多少个，都能使最小的贡献值达到$ 0 $，比如说$ FFFFB $变成$ BEBEB $，$ FFFFFB $变成$ EBEBEB $。同理，$ BFFFF $和$ BFFFFF $也是如此。
2. 那么再来看$ F $的前后缀最大值，即尽可能让相邻的两个字母相同，很明显最大贡献值即为$ F $的个数。
3. 最后再分析一下中间一段$ BFFEFB $的最值。最小贡献值即从左到右进行枚举，将每个$ F $替换成与上一个位置不相同的字母，可以证明此时贡献最小。同理最大贡献值即从左到右进行枚举，将每个$ F $替换成与上一个位置相同的字母。

那么就是说一段字符串的最值可以分为三段来求：前缀都是$ F $的一段的最值+中间一段的最值+后缀都是$ F $的一段的最值。

即：
最小值=前缀$F$的最小贡献值(0)+中间一段$F$的最小贡献值+后缀F的最小贡献值(0)=中间一段$ F $的最小贡献值。
最大值=前缀$F$的最大贡献值(前缀$F$的个数)+中间一段$ F $的最大贡献值+后缀$ F $的最大贡献值(后缀$F$的个数)。

PS：有一种极端的情况，就是给出的字符串里面都是$ F $，这时候可以特判一下，也可以当作只有一个前缀来做，最小值还是0，不过此时最大值不是F的个数了，还要再减去1。

C++代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int n;

int main()
{
    scanf("%d", &n);

    string s, str;
    cin >> s;
    str = s;

    int l = 0, r = n - 1;
    while(l < n && s[l] == 'F') l ++; // 找出第一个不是F的位置，前缀F的个数即为l
    while(r >= 0 && s[r] == 'F') r --; // 找出最后一个不是F的位置，后缀F的个数即为n-1-r

    int minv = 0, maxv = 0;
    int d = 2 - (s[0] == 'F' || s[n - 1] == 'F'); // 求出数列的公差
    for(int i = l; i <= r; i ++) // 贪心出中间一段的最小值
        if(s[i] == 'F') 
        {
            if(s[i - 1] == 'E') s[i] = 'B';
            else s[i] = 'E';
        }

    for(int i = l; i <= r - 1; i ++)
        if(s[i] == s[i + 1]) minv ++;

    for(int i = l; i <= r; i ++) // 贪心出中间一段的最大值
        if(str[i] == 'F') 
            str[i] = str[i - 1];

    for(int i = l; i <= r - 1; i ++)
        if(str[i] == str[i + 1]) maxv ++;

    if(l == n) l --; // 这边的判断可以理解成是不是输入的字符串里面全部都是F
    maxv += l; // 加上前缀F的个数
    if(l <= r) maxv += n - 1 - r; // 加上后缀F的个数，若此时输入为极端情况，此时就不用再加上后缀了

    printf("%d\n", (maxv - minv) / d + 1);
    for(int i = minv; i <= maxv; i += d)
        printf("%d\n", i);

    return 0;
}