4993. FEB
算法
贪心 + 贡献度计算 $O(n)$
时间复杂度
$O(n)$
空间复杂度
$O(n)$
Java 代码
import java.io.*;
import java.util.*;
public class Main{
private static PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
private static String[] strs;
private static Set<Integer> set = new HashSet<>();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
// 公差、首项、末项
int sub = 0, hh = 0, tt = 0;
String s = br.readLine();
char[] ca = s.toCharArray(), cb = new char[n];
for(int i = 0; i < n; i++) cb[i] = ca[i];
// 根据字符串前缀和后缀判断等差数列公差
if(ca[0] == 'F' || ca[n - 1] == 'F') sub = 1;
else sub = 2;
// 前面连续的F可以看做是一个F作为前缀,如‘FFFB’可以看做2 + ‘FB’
while(tt < n - 1 && ca[tt] == 'F') tt++;
for(int i = tt + 1; i < n; i++){
if(ca[i] == 'F'){
cb[i] = cb[i - 1];
// 中间部分,尽可能让首项更小
if(ca[i - 1] == 'E') ca[i] = 'B';
if(ca[i - 1] == 'B') ca[i] = 'E';
}
if(ca[i] == ca[i - 1]) hh++;
if(cb[i] == cb[i - 1]) tt++;
}
int cnt = (tt - hh) / sub + 1;
wt.println(cnt);
for(int i = hh; i <= tt; i += sub){
wt.println(i);
}
wt.close();
}
}