贝西和埃尔希正在密谋最终推翻他们的主人——农夫约翰!他们通过
N
N
N 条短信进行计划。他们的对话可以用一个长度为
N
N
N 的字符串
S
S
S 来表示。
其中
S
i
S_i
Si? 是字母 B
或 E
,这意味着第
i
i
i 条消息分别由贝西或埃尔希发送的。
然而,农夫约翰听说了这个消息,并试图拦截他们的谈话。因此,字符串
S
S
S 的一些字母是 F
,这意味着农夫约翰混淆了信息,发件人未知(贝西、埃尔希都有可能)。
注:约翰没有发送信息!他只是在干扰奶牛间的通话!
未混淆对话的兴奋程度是一只奶牛重复发送信息的次数。也就是说,子串 BB
或 EE
在
S
S
S 中出现的次数。你想找到原始信息的兴奋程度,但你不知道约翰的信息中哪一条实际上是贝西或埃尔希的。在所有可能的情况下,从小到大输出所有可能的兴奋程度。
第一行:一个整数
N
N
N(通话长度)。
第二行:一个字符串
S
S
S(通话内容)。
第一行:输出一个整数
K
K
K,为不同兴奋程度的可能数量。
随后
K
K
K 行:每行一个整数,为每种兴奋程度。注意按照从小到大的顺序输出。
1 ≤ N ≤ 2 × 1 0 5 1 \le N \le 2 \times 10^5 1≤N≤2×105。
DFS、找规律、贪心。
通过 DFS 暴力对拍,我们发现答案为一个等差数列。
不妨设整个序列中仅有一个 F
。
分类讨论这个 F
的位置。
F
在开头此时序列形如 Fxxxxxx
。
不妨设第二位为 E
。
若将 F
变为 E
,则对答案的贡献为
1
1
1。
若将 F
变为 B
,则对答案无贡献。
F
在中间此时序列形如 xxxFxxx
。
F
两侧字符相同。不妨设该字符为 E
,则序列为 xxEFExx
。
若将 F
变为 E
,则对答案的贡献为
2
2
2。
若将 F
变为 B
,则对答案无贡献。
F
两侧字符不同。不妨设此时序列为 xxBFExx
。无论如何替换,对答案的贡献都是 1
。因此下面进行贪心时不考虑这种情况。
F
在结尾。这种情况与情况
1
1
1(F
在开头)相同。证毕。得出结论:答案为一个等差数列,且如果字符串首尾至少一个位置是 F
,那么等差数列的公差为
1
1
1。如果头和尾都不是 F
,那么等差数列公差为
2
2
2。
对于中间的 F
,我们考虑贪心求出等差数列首项与末项。
发现 EB
交替放置时方案数最小,即为数列首项。
同理,相邻的 E
或 B
尽量相同时,方案数最大,即为数列末项。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 300010;
int n, hh, tt;
char s1[N], s2[N];
int main()
{
int sub = 0, hh = 0, tt = 0; // 公差、首项、末项
scanf("%d%s", &n, s1);
if (s1[0] == 'F' || s1[n - 1] == 'F') sub = 1; // 首尾 -> 公差为 1
else sub = 2; // 否则公差为 2
while (tt < n - 1 && s1[tt] == 'F') tt ++ ; // 找到第一个不是 F 的位置开始贪心
for (int i = 0; i < n; i ++ ) s2[i] = s1[i];
for (int i = tt + 1; i < n; i ++ )
{
if (s1[i] == 'F')
{
s2[i] = s2[i - 1]; // 最小值尽量相等
if (s1[i - 1] == 'E') s1[i] = 'B'; // 最大值尽量交替出现
if (s1[i - 1] == 'B') s1[i] = 'E';
}
if (s1[i] == s1[i - 1]) hh ++ ; // 向首项末项累加答案
if (s2[i] == s2[i - 1]) tt ++ ;
}
int k = (tt - hh) / sub + 1; // 计算等差数列项数
printf("%d\n", k);
for (int i = hh; i <= tt; i += sub)
printf("%d\n", i);
return 0;
}