AcWing 4993. FEB
原题链接
困难
作者:
Y.JH
,
2024-01-01 21:26:24
,
所有人可见
,
阅读 116
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
string s;
int main()
{
cin >> n >> s;
if(s == string(n, 'F')) // 特判特殊情况:全是'F'字符
{
cout << n << endl;
for(int i = 0; i < n; i ++)
cout << i << endl;
}
else
{
// 首先排出首尾的'F'字符, 设置双指针设立开头和结尾,考虑中间的情况
int l = 0, r = n - 1;
while(s[l] == 'F') l ++;
while(s[r] == 'F') r --;
// 复制原字符串
auto str = s;
// 设置公差为2的等差数列的最小值和最大值
// 性质:当两个公差为2的等差数列相加时,还是一个等差数列,可以自行证明
int low = 0, high = 0;
//low
for(int i = l + 1; i <= r; i++)
{
if(str[i] == 'F')
{
if(str[i-1] == 'B') str[i] = 'E';
else str[i] = 'B';
}
if(str[i] == str[i-1]) low ++;
}
//high
str = s;
for(int i = l + 1; i <= r; i++)
{
if(str[i] == 'F')
{
str[i] = str[i-1];
}
if(str[i] == str[i-1]) high++;
}
// ends变量表示开头和结尾一共有多少个'F'
// ends计算公式: ends = 开头'F' + 结尾'F' = l + n - 1 - r
int ends = l + n - 1 - r;
// 公差变量
int d = 2;
// 对首尾'F'字符的数量进行判断。
// 性质:当公差为1与公差为2的等差数列相加时,还是为一个公差为1的等差数列
// 且会取到中间的每个数
if(ends == 0) d = 2;
else
{
d = 1;
high += ends;
}
//输出
cout << (high - low) / d + 1 << endl;
for(int i = low ; i <= high; i += d)
cout << i << endl;
}
return 0;
}