FEB

发表于 更新于 分类于 ， 本文字数： 1.2k 阅读时长 ≈ 1 分钟

1.题目

有一个长度为 N的字符串 S，其中的每个字符要么是 B，要么是 E。

我们规定 S的价值等于其中包含的子串 BB 以及子串 EE 的数量之和。

例如，BBBEEE 中包含 2 个 BB 以及 2 个 EE，所以 BBBEEE 的价值等于 4。

我们想要计算 S的价值，不幸的是，在我们得到 S之前，约翰将其中的一些字符改为了 F。

目前，我们只能看到改动后的字符串 S，对于其中的每个 F，我们并不清楚它之前是 B 还是 E。

请你计算，改动前的 S有多少种可能的价值并将所有可能价值全部输出。

输入格式

第一行包含一个整数 N。

第二行包含改动后的字符串 S。

输出格式

第一行输出一个整数 K，表示改动前的 S 的可能价值的数量。

接下来 K 行，按照升序顺序，每行输出一个可能价值。

数据范围

1≤N≤2×10五次方

输入样例1：

1
2
4
BEEF

输出样例1：

1
2
3
2
1
2

输入样例2：

1
2
9
FEBFEBFEB

输出样例2：

1
2
3
2
2
3

输入样例3：

1
2
10
BFFFFFEBFE

输出样例3：

1
2
3
4
3
2
4
6

原题链接

2.思路

题目中说，相邻的两个字母相同则价值+1，比如BBB，他的价值应该是2，而不是1，因为中间的B可以利用两次。另外F是薛定谔的猫状态，既可以当B也可以当E。

我们可以从F字母进行突破,分类讨论。

（情况1：只有F）如果一串字母只有F，类似 FFFF ，k个F,他的价值的最大值和最小值取值应该是非常好算，如果这些F都是B或者都是E，这时候的价值应该是最大的是k-1；不管k为奇数还是偶数，只要这一串字母相邻的两个字母不同，则价值最小值为0.

（情况2：一边有字母）如果一串字母是这样的 ，比如是 B FFFFF 或者是 E FFFFF 或者是 FFFFFB 或者是 FFFFFFE，这几种其实都是属于一种情况。问题来了，这种情况要分奇数偶数吗？我们可以举一个极端一些的例子，可以短时间看出分不分奇数偶数，最小的偶数是0所以最极端的例子就是拿最小的奇数偶数来测试。如果结果是一样的，那么该情况就不分奇数偶数。比如 B + 偶数 最小值显然是0，B+奇数，当奇数为E时最小值依然是0，那么这种情况，取最小值是不分奇数偶数，而且最小值是0.如果是算最大值的话，显然F都是B时最大，所以这种情况是不分奇数偶数，最大值是K。

（情况3：两边有字母，字母且相同）如果一串字母是这样的，B FFFF B 当F =B时，取到最大值是 K +1，而且与奇数偶数无关。如果F是偶数，最小的偶数是0，那么字母将会是BB，此时，偶数最小值是1，如果F是奇数个，最小的奇数是1，那么字母价格会是BEB，那么F为奇数个时，价值最低为0.

（情况4：两边有字母，字母且不同）如果一串字母是这样的，B FFFF E ，（1）当F为奇数个时，最小值是BBE或者BEE，无论如何都是1最小。最大值时BBBBBE或者BEEEEEE，所以最大值是k，（2）当F为偶数个，最小值是0，因为偶数个只要两个F是和两边字母相反的结构时最小，为0.最大值是 K。