自动搬运

查看原文

来自洛谷，原作者为

	Limie **

搬运于2025-08-24 22:46:07，当前版本为作者最后更新于2023-08-24 19:30:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

此题大家都是通过打表的方法找出等差数列的规律，却没有一个人证明，故我用自己的方法给大家讲明白为什么是等差数列。

观察结论

可以发现，如果字符串的开头或结尾是 $F$，则所有可能的情况正好构成一个公差为 $1$ 的等差数列，否则它们会构成一个公差为 $2$ 的等差数列。

那如何证明呢？

（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$，过程也差不多，读者自证不难。

综上，结论正确，证毕！！！

Code：

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int,int> PII;
int n,d=2;
string st;
int l()
{
	int ans=0;
	string t=st;
	for(int i=1;i<n;i++)
		if(t[i]=='F')
			if(t[i-1]=='B')t[i]='E';else t[i]='B';
		
	for(int i=1;i<n;i++)ans+=(t[i-1]==t[i]);
	return ans;
}
int r()
{
	int ans=0;
	string t=st;
	for(int i=1;i<n;i++)
		if(t[i]=='F')t[i]=t[i-1];
	
	for(int i=1;i<n;i++)ans+=(t[i-1]==t[i]); 
	return ans;
}
int main()
{
	int i;
	cin>>n>>st;
	if(st[0]=='F'||st[n-1]=='F')d=1;
	if(st[0]!='F'){
		int x=l(),y=r();
		cout<<(y-x)/d+1<<endl;
		for(i=x;i<=y;i+=d)cout<<i<<endl;
		return 0;
	}
	st[0]='B';
	int x=l(),y=r();
	st[0]='E';
	x=min(x,l());
	y=max(y,r());
	cout<<(y-x)/d+1<<endl;
		for(i=x;i<=y;i+=d)cout<<i<<endl;
}