P9183 题解
Limie
·
·
题解
前言
此题大家都是通过打表的方法找出等差数列的规律，却没有一个人证明，故我用自己的方法给大家讲明白为什么是等差数列。
观察结论
可以发现，如果字符串的开头或结尾是 F ，则所有可能的情况正好构成一个公差为 1 的等差数列，否则它们会构成一个公差为 2 的等差数列。
那如何证明呢？
（1）从简单开始
假设一个最简单的情况：整个序列中有且仅有一个 F 。
- 若 F 在开头：
序列可表示为 F......。
不妨设第二位为 B。
序列可表示为 FB......。
设后面的序列中的兴奋程度（或价值，下文中统一用兴奋程度）为 a。
则总序列可能的兴奋程度为 a 或 a+1。
- 若 F 在中间
若 F 两边的字符相同，不妨设为 B。
则序列为：......BFB.....。
设左边序列兴奋程度为 a，右边为 b。
则兴奋程度可能为：a+b 或 a+b+2。
否则，序列为：.......BFE.....。
设左边序列兴奋程度为 a，右边为 b。
兴奋程度为：a+b+1。
-
总结结论：当 F 在开头或结尾时，公差为 1，否则公差为 2。
（2）数学归纳法
若有 (n-1) 个 F 时，若满足结论，则需证 n 个 F 时也相等。
若开头或结尾没有 F，设原来的兴奋程度的可能值为 a,a+2,a+4,...,a+2k。
将开头或结尾替换成 F，则可能值的变换同简单情况，可能值为：
将中间一个非 $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;
}
```