FEB选择

有一个长度为?N?的字符串?S，其中的每个字符要么是?B，要么是?E。

我们规定?S?的价值等于其中包含的子串?BB?以及子串?EE?的数量之和。

例如，BBBEEE?中包含?22?个?BB?以及?22?个?EE，所以?BBBEEE?的价值等于?44。

我们想要计算?S?的价值，不幸的是，在我们得到?S?之前，约翰将其中的一些字符改为了?F。

目前，我们只能看到改动后的字符串?S，对于其中的每个?F，我们并不清楚它之前是?B?还是?E。

请你计算，改动前的?S?有多少种可能的价值并将所有可能价值全部输出。

输入格式

第一行包含一个整数?N。

第二行包含改动后的字符串?S。

输出格式

第一行输出一个整数?K，表示改动前的?S?的可能价值的数量。

接下来?K?行，按照升序顺序，每行输出一个可能价值。

数据范围

1≤N≤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

思路：分情况讨论当F为E或者是B时对得分的影响

?分好情况后，我们看两端和中间，两端算一次，中间算一次。、

然后合并，需要注意合并的时候，公差都为2的两个数列合并后还是公差为2的数列，一个为1一个为2合并后公差为1。

两端其实就是情况2，代码如下：

int l=0,r=n-1;
    while(s[l]=='F')l++;
    while(s[r]=='F')r--;
int ends=l+n-1-r,d=2;
    if(ends)high+=ends,d=1;

中间的话最大值就是使所有的F为相同的E或者B，最小就是使B和E交替出现。代码如下：

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]==str[i-1])low++;
            
        }
        
        str=s;
        for(int i=l;i<=r;i++)
        {
            if(str[i]=='F')str[i]=str[i-1];
            if(i>l&&str[i]==str[i-1])high++;
        }

完整代码：

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int n;
string s;
int main(){
    cin>>n>>s;
    if(s==string(n,'F')){
        cout<<n<<endl;
        for(int i=0;i<n;i++){
            cout<<i<<endl;
        }
    }
    else {
        
        int l=0,r=n-1;
        while(s[l]=='F')l++;
        while(s[r]=='F')r--;
        string str=s;
        int low=0,high=0;
        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]==str[i-1])low++;
            
        }
        
        str=s;
        for(int i=l;i<=r;i++)
        {
            if(str[i]=='F')str[i]=str[i-1];
            if(i>l&&str[i]==str[i-1])high++;
        }
        int ends=l+n-1-r,d=2;
        if(ends)high+=ends,d=1;
        cout<<(high-low)/d+1<<endl;
        for(int i=low;i<=high;i+=d){
            cout<<i<<endl;
        }
    }
}

类似题目
l填充‘？’01-CSDN博客