题目描述
有一个长度为 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 * 10^5\)
样例
输入样例1：
4
BEEF
输出样例1：
2
1
2
输入样例2
9
FEBFEBFEB
输出样例2：
2
2
3
输入样例3：
10
BFFFFFEBFE
输出样例3
3
2
4
6
题解
我们将本题的B、E改写为0，1，F为x，方便后面讨论
分段考虑这道题目，变化在于x的变化
分4种情况
第1种情况，xxxxxxx(k)情况的可能取值：k-1, k-2, k-3,..., 0; min = 0，max = k-1; d = 1;
第2种情况，0xxxxxx(k)情况的可能取值：k, k-1, k-2,..., 0; min = 0, max = k; d = 1;
第3种情况，0xxxxx0(k)情况的可能取值：k为奇数：k+1, k-1, k-3,..., 0; min = 0, max = k+1; d = 2;
k为偶数：k+1, k-1, k-3,...,1; min = 1, max = k+1; d = 2
第4种情况，0xxxxx1(k)情况的可能取值：k为奇数：k, k-2, k-3,..., 1; min = 1, max = k; d = 2;
k为偶数：k, k-2, k-3,..., 0; min = 0, max = k; d = 2;
考虑如何合并公差为2的等差数列，两个数列合并后的结果是，min = min_a + min_b, max = max_a + max_b, 公差为2的等差数列
考虑如何合并公差为1的等差数列，两个数列合并后的结果是，min = min_a + min_b, max = max_a + max_b, 公差为1的等差数列
考虑如何合并公差为1和公差为2的等差数列，两个数列合并的结果是，min = min_a + min_b, max = max_a + max_b, 公差为1的等差数列
1.先特判情况1和n=1的情况
2.再算出中间段的情况3和4，合并公差为2等差数列
3.算两边的公差为1的情况
4.最终合并公差为1和2的情况
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define SZ(v) ((int)v.size())
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
using namespace std;
const int N = 1e6;
int _;
int n;
string s;
int ans;
int min_1, min_2, max_1, max_2;
void solve() {
cin >> n >> s;
if(n == 1) {
cout << 0 << "\n";
return;
}
// 情况1
if(s == string(n, 'F')) {
cout << n << "\n";
for(int i = 0; i <= n - 1; i++) {
cout << i << "\n";
}
return;
}
// 算固定值
for(int i = 1; i < n; i++) {
if(s[i] != 'F' && s[i-1] != 'F' && s[i] == s[i-1]) {
ans++;
}
}
// 算两边公差为1的值
// 算左边为'F'的一段
int sum = 0;
for(int i = 0; i < n && s[i] == 'F'; i++) {
sum++;
}
max_1 += sum;
// 算右边为'F'的一段
sum = 0;
for(int i = n - 1; i >= 0 && s[i] == 'F'; i--) {
sum++;
}
max_1 += sum;
// cout << max_1 << '\n';
// 情况2，3，4
int l = -1, r = -1;
int k;
for(int i = 0; i < n; i++) {
if(s[i] == 'F') {
if(l == -1) {
l = r = i;
}
} else if(l != -1) {
r = i - 1;
k = (r - l + 1);
// cout << "l = " << l << " " << "r = " << r << "\n";
if(l != 0 && r + 1 != n) {
if(s[l - 1] == s[r + 1]) {
if(k & 1) {
max_2 += k + 1;
} else {
min_2 += 1;
max_2 += k + 1;
}
} else {
if(k & 1) {
min_2 += 1;
// cout << "min_2 = " << min_2 << "\n";
max_2 += k;
} else {
max_2 += k;
}
}
}
l = -1;
}
}
if(max_1 == 0) {
cout << (max_2 - min_2 + 2) / 2 << "\n";
for(int i = min_2; i <= max_2; i += 2) {
cout << ans + i << "\n";
}
return;
}
min_1 += min_2;
max_1 += max_2;
cout << max_1 - min_1 + 1 << "\n";
for(int i = min_1; i <= max_1; i++) {
cout << ans + i << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
_ = 1;
// cin >> _;
while(_--) {
solve();
}
return 0;
}