题意
给定一个只含‘E’、’B’、’F’的字符串,F可以被修改为E或B,求最终转化为没有‘F’的字符串中含有“EE”、“BB”的子串个数和的各种情况
思路
通过找规律可以发现最终的结果是一段等差数列,然后列举F的情况:
首尾的F转变为E或B可以给答案增加0或1的贡献
对于中间的F,若两边相同,转变为E或B可以给答案增加0或2的贡献;若两边不同,可以给答案增加1的贡献,这种F可以直接当作E或者B来看
所以可以得出结论,如果首尾有F,那公差为1,否则公差为2,因此我们只需贪心的求最小值和最大值即可。然后,对于一连串的F,最小值尽可能间隔着以EBEBEB的形式放,最大值尽可能以EEE或BBB的形式放:对于情况1,最小值只要和最近的非F字符不同即可,可以做到贡献为0,最大值和最近的非F字符相同即可
对于情况2,最小值由于需要间隔放,考虑到F串的左右两边相同或否,需要根据奇偶判断贡献为1/0;最大值无论和左边相同还是和右边相同结果一样