AAAB, 我太爱你了! 看错题debug了3个小时
题目描述
B. I love AAAB
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Let’s call a string good if its length is at least 2 and all of its characters are A except for the last character which is B. The good strings are AB,AAB,AAAB,…. Note that B is not a good string.
You are given an initially empty string s1.
You can perform the following operation any number of times:
Choose any position of s1 and insert some good string in that position.
Given a string s2, can we turn s1 into s2 after some number of operations?
Input
Each test contains multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single string s2 (1≤|s2|≤2⋅105).
It is guaranteed that s2 consists of only the characters A and B.
It is guaranteed that the sum of |s2| over all test cases does not exceed 2⋅105.
Output
For each test case, print “YES” (without quotes) if we can turn s1 into s2 after some number of operations, and “NO” (without quotes) otherwise.
You can output “YES” and “NO” in any case (for example, strings “yEs”, “yes” and “Yes” will be recognized as a positive response).
样例
input
4
AABAB
ABB
AAAAAAAAB
A
output
YES
NO
YES
NO
算法1
思路
这题题面很简单,就是每个B前面至少得有一个A,且结尾必须是B,如果是就是YES,否则就NO
但是要注意的是AABB,AAABB也是可以的,我刚开始误认为只有AAAB,AAAB,AAB,诸如此类的才叫好串
没想到AABB只需要在AB直接插入AB就行了……太笨了
所以本题思路就是
先检查一下结尾是否为B
然后遍历字符串,如果在字符串或者它的前缀字串中B出现的次数比A多说明绝对不是一个好串,例如ABB,AABBB
C++ 代码
#include <iostream>
#include <string>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
string a;
cin >> a;
int len = a.size();
int ans = 0;
bool flag = false;
if(a[len - 1] == 'A')
{
puts("No");
continue;
}
for(int i = 0; i < len; i++)
{
if(a[i] == 'B') ans --;
else ans ++;
if(ans < 0)
{
puts("No");
flag = true;
break;
}
}
if(!flag)
puts("Yes");
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla