AcWing 4993. FEB
原题链接
困难
核心思想:分类讨论
下面的k为F的个数
case1: 当字符串全为F时,价值的可能的取值为0,1,....,k - 1
case2: 当字符串为0FFFFFFF时,价值的可能取值为0,1,.....k
case3: 当字符串为0FFFFFFF0时,不管是哪种情况,最大一定是价值k + 1
当k为偶数时,最小价值为1,价值取值为k + 1,k - 1, k - 3, k - 5 ........ 1,公差d=2
当k为奇数时,最小价值为0,价值取值为k + 1,k - 1, k - 3, k - 5 ........ 0,公差d=2
case4: 当字符串为0FFFFFFF1时,不管哪种情况,最大价值一定是k
当k为偶数时,最小价值为0,价值取值为k, k - 2, k - 4, … 1,公差d=2
当k为奇数时,最小价值为1,价值取值为k, k - 2, k - 4, … 0,公差d=2
当然其实case3与case4没必要这么麻烦
怎么求最大?F替换成与前面一样的即可
怎么求最小?F替换成与前面相反的即可
合并两个数列
合并d=2与d=2的数列时,得到一个新的数列d=2,min = min1 + min2,max = max1 + max2
合并d=1与d=2的数列时,同上
合并d=1与d=1的数列时,得到一个新的数列d=1,min = min1 + min2,max = max1 + max2
最终做法:
1、求中间 2、求两边 3、合并
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static String repeat(int n, char c) { // 重复n次字符c的字符串
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(c);
return sb.toString();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
char[] s = sc.next().toCharArray();
if (new String(s).equals(repeat(n, 'F'))) { // 如果全是F的情况,直接计算
System.out.println(n);
for (int i = 0; i < n; i++) System.out.println(i);
} else {
// 跳过左右两边的F
int l = 0, r = n - 1;
while (s[l] == 'F') l++;
while (s[r] == 'F') r--;
// 分别求最小、最大
int min = 0, max = 0;
char[] copy = Arrays.copyOf(s, s.length); // 由于需要计算两次,所以要拷贝一份
for (int i = l; i <= r; i++) {
if (copy[i] == 'F') {
if (copy[i - 1] == 'B') copy[i] = 'E';
else copy[i] = 'B';
}
if (i > l && copy[i] == copy[i - 1]) min++;
}
copy = Arrays.copyOf(s, s.length);
for (int i = l; i <= r; i++) {
if (copy[i] == 'F') {
if (copy[i - 1] == 'B') copy[i] = 'B';
else copy[i] = 'E';
}
if (i > l && copy[i] == copy[i - 1]) max++;
}
// 加上前面的左右两段。只要前面两段任意有一段存在F,那么就会改变最终的输出公差为1
// 只需要改变max即可,因为case3的最小值都一定是0
int ends = l + n - r - 1;
int d = 2;
if (ends != 0) {
d = 1; // 只要左右有一段随意的x,那么合并之后的公差就为1 (已经证明过)
max += ends;
}
System.out.println((max - min) / d + 1);
for (int i = min; i <= max; i += d) System.out.println(i);
}
}
}