题目描述
有一个长度为 N 的字符串 S,其中的每个字符要么是 B,要么是 E。
我们规定 S 的价值等于其中包含的子串 BB 以及子串 EE 的数量之和。
例如,BBBEEE 中包含 2 个 BB 以及 2 个 EE,所以 BBBEEE 的价值等于 4。
我们想要计算 S 的价值,不幸的是,在我们得到 S 之前,约翰将其中的一些字符改为了 F。
目前,我们只能看到改动后的字符串 S,对于其中的每个 F,我们并不清楚它之前是 B 还是 E。
请你计算,改动前的 S 有多少种可能的价值并将所有可能价值全部输出。
算法
等差数列计算
C++ 代码
#include <iostream>
#include <string>
using namespace std;
#define int long long
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int N;
string Str;
cin >> N >> Str;
// 情况1 全为F
if (Str == string(N, 'F')) {
cout << N << "\n";
for(int i = 0; i < N; ++ i) cout<< i << "\n";
return 0;
}
// 情况2 两侧的F
int LVal = 0; // 左侧F
int RVal = 0; // 右侧F
for (int i = 0; i < Str.size(); ++i) {
if (Str[i] == 'F') LVal++;
else break;
}
for (int i = Str.size() - 1; i >= 0; --i) {
if (Str[i] == 'F') RVal++;
else break;
}
int CVal = 0;
// 情况3 中间的F
int Fmin = 0; // 最小值
int Fmax = 0; // 最大值
for (int i = LVal, j = i + 1; j <= N - 1 - RVal; ++i, ++j) {
// F个数
int num = 1;
if (Str[i] == Str[j] && Str[j] != 'F') ++CVal;
if (Str[j] == 'F') {
do
{
j++;
// 下一个为F
if (Str[j] == 'F')num++;
// 下一个不为F
else {
// 两边相同
if (Str[i] == Str[j]) {
// 偶数
if (num % 2 == 0) {
Fmin += 1;
Fmax += num + 1;
}
// 奇数
else {
Fmin += 0;
Fmax += num + 1;
}
}
// 两边不同
else {
// 偶数
if (num % 2 == 0) {
Fmin += 0;
Fmax += num;
}
// 奇数
else {
Fmin += 1;
Fmax += num;
}
}
}
}
while (Str[j] == 'F');
i = j - 1;
}
}
int d = 2; // 公差
if (LVal + RVal != 0) --d;
Fmin += CVal;
Fmax += (LVal + RVal + CVal);
cout << (Fmax - Fmin) / d + 1<< "\n";
for (int i = Fmin; i <= Fmax; i += d) cout << i << "\n";
return 0;
}