题意
有一个长度为 $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×105$
样例
输入样例1:
4
BEEF
输出样例1:
2
1
2
输入样例2:
9
FEBFEBFEB
输出样例2:
2
2
3
输入样例3:
10
BFFFFFEBFE
输出样例3:
3
2
4
6
证明
- 最优解做法
- 答案为等差数列
拆解
拿到读入的字符串后, 我们可以将它解剖开来(好残忍), 让其只有一组 F
如:$BEEF$ 可以拆为 $BE + EF$
$FEBFEBFEB$ 可以拆为 $FE + BFE + BFE + B$
$BFFFFFEBFE$ 可以拆为 $BFFFFFE + BFE$
好, 现在已经有三个样例自bei愿puo献出了自己, 让我们观察一下
分类讨论
🆗 相信你已经有头绪了, 让我们再深入探索一下规律 下辈子再来探索吧
- 每一个字符串都能拆为若干个小字符串
废话 - 不含 $F4 的字符串是不可修改的, 固定存在的, 所以可以忽略
礼貌:你字符吗? - 包含 $F$ 又有几种情况: $F$ 在两边, $F$在中间 重点
- 还有另一种可能, 就是全都是 $F$ 如 $FFFFF$
一:全为 $F$
最值: $0, k-1$ (k为字符串长度, 下同)
若后面每一项与前面 不同 , 取到最小值$0$
若后面每一项与前面 相同 , 取到最大值$k-1$
以 FFFFF 为例
$BBBBB => 4$
$BBBBE => 3$
$BBBEB => 2$
$BBEBE => 1$
$BEBEB => 0$
此时公差为1
二:不全为F
按照分类讨论的结果来看,有两种情况
- F 在两边
F在两边, 意味着它们一定在字符串边缘(因为有一遍没有字符)
同时有具有对称性, 即F无论在左侧还是右侧, 都可以通过对称得到
如 $FFFFB$ 与 $BFFFF$ 并没有本质差别, 前者能做到的, 后者也可以(其实你也可以)
又因为 $F$ 可以变为 $B$ 或 $E$ , 那么具有相似性 即 $FFFFB$ 与 $FFFFE$ 就有相同的结果
故后来只讨论形如 $BFFF$ 的例子
好了, 讨论的范围又少了好多废话也多了不少
最值: $0, k-1$若后面每一项与前面 不同 , 取到最小值$0$
若后面每一项与前面 相同 , 取到最大值$k-1$
举例同上
以 BFFFF 为例
$BBBBB => 4$
$BBBBE => 3$
$BBBEB => 2$
$BBEBE => 1$
$BEBEB => 0$
此时公差为$1$, -
F 在中间
其实这反而是常见的情况
对称性和相似性同上F在两边, 意味着它们一定在字符串边缘(因为有一遍没有字符)
同时有具有对称性, 即F无论在左侧还是右侧, 都可以通过对称得到
如 $EFFFB$ 与 $BFFFE$ 并没有本质差别, 前者能做到的, 后者也可以
又因为 $F$ 可以变为 $B$ 或 $E$ , 那么具有相似性 即 $BFFFB$ 与 $EFFFE$ 就有相同的结果但是, 有勤奋的孩子经过尝试可以拿到
$BFFFB, BFFFFB$和我们讨论的结果有很大差别(其实不大)
$BFFFB => 0, 2, 4 BFFFFB => 1, 3, 5$- 它们的公差是 $2$ , 而不是之前讨论的 $1$
- 它们首项不同
- 但是都是等差数列
其实这与其 $F$ 个数的奇偶性以及首位项是否相同有关
当首尾相同时
当 $F$ 为奇数个, 首项为$0$; 偶数个, 首项为$1$
当首尾不同时
当 $F$ 为奇数个, 首项为$1$; 偶数个, 首项为$0$
最值: $0/1, k-1/k$
答案组合
单蹦的字符串已经处理完了, 现在是将其合并了(其实你能看到这已经不容易了)
(一下需要一定数学, 不想看跳过)
经过讨论, 这里是公差为$1$ 和公差为$2$ 的等差数列合并
一下先处理两个数列合并
- 若公差均为$1$ 或 公差均为$2$
显然,最小值是两最小值之和, 最大值是两最大值之和, 公差为$1$ - 若公差为$1$和公差为$2$
最值同上, 处理公差
$$ a_1, a_2 … a_n (公差为1)\\ b_1, b_2 … b_m (公差为2)\\ 最大值: a_n + b_m\\ 次大值: a_{n-1} + b_m (比前者少1)\\ 再小 : a_n + b_{m-1} (比前者又少一)\\ $$
很显然, 在 $n,m >= 2$ 时
$a, b$两序列合并后公差为&1$ 故只要有公差为$1$的序列, 即情况 二1 存在 答案就为公差为一的等差数列
可算讨论完了(鼓掌声)(气喘吁吁)
不过真的有看到这的吗?
如果有的话,那你真是太棒了
代码实现(C艹)
#include <bits/stdc++.h>
using nsmespsce std;
int n;
string s;
int msin(){
cin >> n >> s;
//第一种情况: 全是F (约翰真好)
if (s == string(n, 'F')){
//这种时候 0 ~ n-1 的每一个数都能取到, 故有 n 中情况
cout << n << endl;
for (int i = 0;i < n;i ++)
printf ("%d\n", i);
}
//第二种情况: 不全是F (废话)
else{
//首先把左右两端的 $F$ 去掉
int l = 0,r = n - 1;
while (s[l] == 'F') l ++;
while (s[r] == 'F') r --;
//low => 最小值 high =>最大值
int low = 0, high = 0;
string str = s; //做个备份, 后面用
//先计算最小值
//将每一个 $F$ 改为与前一个不相同的字符, 得到最小值
for (int i = l;i <= r;i ++){
if (str[i] == 'F')
if (str[i - 1] == 'B') str[i] = 'E';
else str[i] = 'B';
//如果有相同的, 最值加一
if (i > l && str[i - 1] == str[i]) low ++;
}
//得到最小值了, 将备份覆盖 (卸磨杀驴)
str = s;
//再计算最大值
//将每一个 $F$ 改为与前一个 相同 的字符, 得到最大值
for (int i = l;i <= r;i ++){
if (str[i] == 'F') str[i] = str[i - 1];
//如果有相同的, 最值加一
if (i > l && str[i - 1] == str[i]) high ++;
}
// n-1-r => 右端 $F$ 的个数, d => 公差
int ends = l + n - 1 - r, d = 2;
//如果两端存在 F, 最大值加上 F, 公差变1
if (ends)high += ends, d --;
//项数 = (尾项 - 首项) / 公差 + 1
cout << (high - low) / d + 1 << endl;
for (int i = low; i <= high;i += d)
printf ("%d\n", i);
}
return 0;
}
首赞首收藏和沙发归作者