P9183 [USACO23OPEN] FEB B 题解

KidA · 2023-10-09 16:21:30 · 题解

由于只需要考虑相邻的位置，所以每一段连续的 F 是互不影响的，可以分别进行考虑。而连续的一段 F 又可以分成两类：靠边的和被夹在中间的。

靠边的 F 段较为简单，假定有 c 个 F ，不难发现只要让 EB 交错出现就可以达到最少次数 ，而让所有的 F 都变成最近的非 F 就可以达到最多次数 c，由内向外减少交错的长度就可以逐渐增加次数，使得 [0,c] 中的任意次数都是可行的。

夹在中间的 F 段稍微复杂一些，段的长度与两边字符的异同都会影响答案，不过还是可以先用贪心按顺序考虑每个 F ，分别尽量保持不同和尽量保持不变就可以求出最少次数 l 和最大次数 r。接下来再进行调整并观察可能的次数，不难发现每次调整都会使得答案刚好变化 2。

综上所述，我们可以对每一段的下界和上界分别进行累加，就得到了最终答案的下界与上界。若只有夹在中间的 F 段，那么次数变化的步长为 2，否则只要有任意靠边的 F 段，就可以让变化的步长变成 1，由此可以算出次数的数量，最后进行输出即可。

实现时不需要分段进行处理，通过判断首字母与末字母是否为 F 就可以知道是否有靠边的段，然后直接贪心求解上下界即可。

时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;

int n;
int l,r,d;
string s,t;

int main(){
    cin>>n>>s,t=s;
    d=2-(s[0]=='F'||s[n-1]=='F');
    for(;r<n-1&&s[r]=='F';r++);
    for(int i=r+1;i<n;i++){
        if(s[i]=='F')
            t[i]=t[i-1],s[i]=(s[i-1]=='E'?'B':'E'); 
        l+=(s[i]==s[i-1]),r+=(t[i]==t[i-1]); 
    } 
    cout<<(r-l)/d+1<<'\n';
    for(int i=l;i<=r;i+=d) cout<<i<<'\n';
    return 0;
}