每天随机做一道CF题并写题解，希望有朝一日能拿块牌子(rating:1300~1800)
原题链接：Codeforces 550A-Two Substrings
题意：给你一个字符串s，你需要判断字符串s中是否含有子串"BA"和"AB"，且这两个子串是不重叠的。
思路：对于字符串s，"BAB"和"ABA"都可以被认为是"BA"和"AB"中的任意一种，所以只需要统计s中"ABA","BAB","AB"和"BA"的出现次数就可以做出判断。
- 当"ABA"与"BAB"的出现次数大于等于2时，令其中一个取"AB"，另一个取"BA"即可
- 当"ABA"与"BAB"的出现次数仅有一次时，判断"AB"和"BA"的出现次数，令其等于没有出现过的即可
- 当"ABA"与"BAB"没有出现过时，需要字符串中既包含"AB"又包含"BA"
代码如下：
点击查看代码
//Author:Fczhao
//Language:cpp
#include <bits/stdc++.h>
using namespace std;
signed main() {
ios::sync_with_stdio(false);
string s; cin >> s;
int n = s.length();
int ab = 0, ba = 0, all = 0;
for(int i = 0; i < n - 1; i++) {
if(s.substr(i, 3) == "ABA") {
all++;
i += 2;
}
else if(s.substr(i, 3) == "BAB") {
all++;
i += 2;
}
else if(s.substr(i, 2) == "AB") {
ab++;
i++;
}
else if(s.substr(i, 2) == "BA") {
ba++;
i++;
}
}
if(all >= 2) cout << "YES" << endl;
else if(all >= 1 && (ab || ba)) cout << "YES" << endl;
else if(ab && ba) cout << "YES" << endl;
else cout << "NO" << endl;
return 0;
}
本题标签：字符串 模拟 贪心