未完成
题目描述
有一个长度为 $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 \\le N \\le 2 \\times 10^5$
输入样例1:
4
BEEF
输出样例1:
2
1
2
输入样例2:
9
FEBFEBFEB
输出样例2:
2
2
3
输入样例3:
10
BFFFFFEBFE
输出样例3:
3
2
4
6
题意简化
给定长度为 $n$ 的字符串 $S$ ,含有 $B$、$E$、$F$ 三种字符,则 $S$ 的价值为 $BB$、$EE$ 子串数量。
其中 $F$ 为不确定字符,可更换为 $B$ 或 $E$。
问 $S$ 在替换掉所有 $F$ 之后可能的价值。
题外话
写到一半然后 $SAI2$ 崩了,于是我重启了电脑。
但忘记没保存题解。。。
这次用黑底手写,自我感觉很好看QwQ。
算法1
(模拟+贪心) $O(n^2)$
为了方便描述,我们
将 $B$ 记为 $0$
将 $E$ 记为 $1$
将 $F$ 记为 $x$
我们列出解题步骤:
- 先分析每一段连续的 $x$ 的价值有哪些;
- 再分析所有段的价值之和有哪些。
那接下来我们开始分类讨论:
情况一:
字符串 $S$ 中只含有 x
。
情况二:
字符串 $S$ 的最左端或最右端有固定值,其余为 x
。
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla