PTA模拟+数学分析
作者 李曲
单位 浙江工业大学
生物学家发现了一种奇怪的DNA分子，最好用集合{A，B}中的N个字符序列来描述。一个不太可能的突变序列导致了一条由A‟s组成的DNA链。生物学家发现这很奇怪，所以他们开始更详细地研究突变。
他们发现了两种类型的突变。一种类型导致改变序列的单个字符（A→B还是B→A） 。第二种类型更改序列的整个前缀，特别是用另一个字符（A替换B，B替换A）替换从1到K位置的所有字符（对于1和N之间的一些K，包括）。
计算可能将起始分子转化为终态（仅包含一个字符）的最小突变数。突变可以以任何顺序发生。
输入格式:
输入的第一行包含正整数N（1≤N≤1000），表示分子的长度。
第二行输入包含一个包含N个字符的字符串，每个字符可以是A或B。
这个字符串代表分子的起始状态。
输出格式:
第一行输出必须包含所需的最小突变数。
输入样例1:
4
ABBA
输出样例1:
2
输入样例2:
5
BBABB
输出样例2:
2
输入样例3:
12
AAABBBAAABBB
输出样例3:
4注意要点：如果有连续两个B就区间翻转，否则只翻转单个字符。
把字符串翻转，然后从前往后跑，模拟翻转。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"ll n;
string s;void solve(){cin >> n >> s;reverse(s.begin(),s.end());ll sum=0,c=0;//c为翻转次数for(ll i = 0 ; i < s.size() ; i ++){if(s[i] == 'B' && s[i+1] == 'B' && c%2 == 0){sum++;c++;}else if(s[i] == 'A' && s[i+1] == 'A' && c%2 == 1){sum++;c++;}else if(s[i] == 'B' && c%2 == 0){sum++;}else if(s[i] == 'A' && c%2 == 1){sum++;}}cout << sum << endl;return;
}int main(){ll t=1;//cin >> t;while(t--)solve();return 0;
}