C/C++教程

【Codeforces】550A-Two Substrings

本文主要是介绍【Codeforces】550A-Two Substrings,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

每天随机做一道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;
}

本题标签:字符串 模拟 贪心

这篇关于【Codeforces】550A-Two Substrings的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!