原题链接:AcWing.4993/Luogu
这题出的非常好,你以为我下面要讲这个题了——对,我就是要讲这个题,但是不同于网上千篇一律的找规律,我这次会给出为什么是等差数列的简单证明。
(1)从简单开始
假设一个最简单的情况:整个序列中只有一个$F$。
$1.$若$F$在开头:
序列可表示为$F......$。
不妨设第二位为$B$。
序列可表示为$FB......$。
设后面的序列中的兴奋程度(或价值,下文中统一用兴奋程度)为$a$。
则总序列可能的兴奋程度为$a$或$a+1$。
$2.$若$F$在中间
若$F$两边的字符相同,不妨设为$B$。
则序列为:$......BFB.....$。
设左边序列兴奋程度为$a$,右边为$b$。
则兴奋程度可能为:$a+b$或$a+b+2$
否则,序列为:$.......BFE.....$,
设左边序列兴奋程度为$a$,右边为$b$。
兴奋程度为:$a+b+1$
$3.F$在结尾:同第$1$种。
总结结论:当$F$在开头或结尾时,公差为$1$,否则公差为$2$。
(2)数学归纳法
若有$(n-1)$个$F$时,若满足结论,则需证$n$个$F$时也相等。
若开头或结尾没有$F$,设原来的兴奋程度的可能值为$a,a+2,a+4,…,a+2k$。
将开头或结尾替换成$F$,则可能值的变换同简单情况,可能值为:$a,a+2,a+4,…,a+2k,a+1,a+3,…,a+2k+1$,即$a,a+1,a+2,a+3,…,a+2k+1$即公差为$1$的等差序列。
将中间一个非$F$的位置换成$F$,过程也差不多,读者自证不难。
综上,结论正确,证毕!!!