D. Linguistics(思维 + 贪心)

Problem - D - Codeforces

 Alina发现了一种奇怪的语言，它只有4个单词:a, B, AB, BA。事实也证明，在这种语言中没有空格:一个句子是通过将单词连接成一个字符串来写的。Alina发现了一个这样的句子，她很好奇:有没有可能它恰好由a个单词a, b个单词b, c个单词AB和d个单词BA组成?换句话说，确定是否有可能以某种顺序连接这些a +b+c+ d单词，从而得到的字符串是s。每个a +b+c+ d单词必须在连接中精确地使用一次，但您可以选择它们连接的顺序。输入输入的第一行包含一个整数t (1 < t < 105)——测试用例的数量。测试用例的描述如下。每个测试用例的第一行包含四个整数a, b, c, d (0 < a, b, c, d < 2 - 105)——单词a, b, AB, BA分别必须在句子中使用的次数。第二行包含字符串s (s仅由字符A和B组成，1 <|s <2 -105， |s| = A + B + 2c+ 2d) -句子。注意，条件|s| =a +b+2c+2d(这里|s|表示字符串s的长度)等价于这样一个事实，即s与a+b+ c+d单词的连接一样长。s对所有测试用例的长度之和不超过2-105。输出对于每个测试用例，如果有可能句子s恰好由a个单词a、b个单词b、c个单词AB和d个单词BA组成，则输出YES，否则输出NO。您可以在任何情况下输出每个字母。例子

input

Copy

8
1 0 0 0
B
0 0 1 0
AB
1 1 0 1
ABAB
1 0 1 1
ABAAB
1 1 2 2
BAABBABBAA
1 1 2 3
ABABABBAABAB
2 3 5 4
AABAABBABAAABABBABBBABB
1 3 3 10
BBABABABABBBABABABABABABAABABA

output

Copy

NO
YES
YES
YES
YES
YES
NO
YES

请注意在第一个测试用例中，句子s是b，很明显，它不可能由一个单词a组成，所以答案是NO。在第二个测试用例中，句子s是AB，它有可能由一个单词AB组成，所以答案是YES。在第三个测试用例中，句子s是ABAB，它有可能由一个单词A，一个单词B和一个单词BA组成，asA+ BA +B = ABAΒ。在第四个测试用例中，句子s是ABAAB，它有可能由一个单词A，一个单词AB和一个单词BA组成，asA+ ba + ab = abaab。在第五个测试用例中，句子s是BAABBABBAA，它有可能由一个单词A，一个单词B，两个单词AB和两个单词组成单词BA，如BA + AB + B + AB + BA + A = BAABBABBAA。

题解:
1.首先判断字母个数是否满足要求

如果由于字符串长度与四个数和相等,所以只要判断其中A是否满足即可,

2.我么肯定要先满足组成AB , BA的需要

如果这两个满足结合之前判断的剩下的A,B一定够

我们截取连续一段不同的类似

ABABA...

BABAB...

只有这种才能满足组成AB和BA的需要

如果这种字符串长度为奇数那么,可以组成n/2个AB,或n/2个BA

所以当为奇数时是可以随便分配BA,AB的记录下来

然后为偶数时分别记录开头为A或B的

那么我们截取了这么多子串,应该先从长串开始还是从短串开始分配?

a,b,c,d取 1 1 2 3
字符串取 ABABABBAABAB

按照上诉思路，我们拆分字符串为ABABAB, BA, ABAB这3种子串。

如果先消费ABABAB，由于优先分配给AB，ABABAB剩下AB，再分配给BA，此时贡献0个BA。后边的BA,ABAB总共贡献BA个数为2，不能满足要求。

而如果先消费ABAB, 由于优先分配给AB，ABAB刚好分配2个AB。后边ABABAB, BA再去分配BA，就有3个了，可以满足要求。

我们发现，优先消费短字符串，可以让更长的字符串给另一种类型做消费
 

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define int long long
const int N = 1e6 + 10;
pair<int, int> p[N];
typedef pair<int, int> PII;
int mod = 1e9 + 7;
string s; 
void check(int &fir,int x,int &sec)
{if(fir >= x){fir -= x;}else{x -= fir + 1;fir = 0;sec -= min(sec,x);}
}
void solve() 
{int a,b,c,d;cin >> a >> b >> c >> d;int na = 0;cin >> s;for(int i = 0;s[i]; i++){if(s[i] == 'A')na++;}if(na != a + c+d){cout<<"NO\n";return ;}int n = s.size();vector<int> sa,sb;int i = 0;int cnt = 0;while(i < n){int j = i + 1;while(j < n&&s[j] != s[j-1]){j++;}int len = j - i;if(len == 1){i = j;continue;}if(len&1){cnt += len/2;}else{len /= 2;if(s[i] == 'A'){sa.push_back(len);}else{sb.push_back(len);}}i = j;} sort(sa.begin(),sa.end());sort(sb.begin(),sb.end());for(auto len:sa){check(c,len,d);}	for(auto len:sb){check(d,len,c);}if(cnt >= c + d){cout << "Yes\n";}else{cout <<"No\n";}
}
signed main() 
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);int t = 1;cin >> t;
//scanf("%lld",&t);while (t--) {solve();}
}
//3 F
//5 B
//6 F
//9 F
//10 B
//12 F
//15 FB
//18 FB