天津市工程建设交易管理中心网站,网络科技公司一般做什么,做城市网站的标语,网站品牌推广公司Problem - D - Codeforces Alina发现了一种奇怪的语言#xff0c;它只有4个单词:a, B, AB, BA。事实也证明#xff0c;在这种语言中没有空格:一个句子是通过将单词连接成一个字符串来写的。Alina发现了一个这样的句子#xff0c;她很好奇:有没有可能它恰好由a个单词a, b个单…Problem - D - Codeforces Alina发现了一种奇怪的语言它只有4个单词:a, B, AB, BA。事实也证明在这种语言中没有空格:一个句子是通过将单词连接成一个字符串来写的。Alina发现了一个这样的句子她很好奇:有没有可能它恰好由a个单词a, b个单词b, c个单词AB和d个单词BA组成?换句话说确定是否有可能以某种顺序连接这些a bc d单词从而得到的字符串是s。每个a bc 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 b2c2d(这里|s|表示字符串s的长度)等价于这样一个事实即s与ab cd单词的连接一样长。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
BBABABABABBBABABABABABABAABABAoutput
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由于优先分配给ABABABAB剩下AB再分配给BA此时贡献0个BA。后边的BA,ABAB总共贡献BA个数为2不能满足要求。
而如果先消费ABAB, 由于优先分配给ABABAB刚好分配2个AB。后边ABABAB, BA再去分配BA就有3个了可以满足要求。
我们发现优先消费短字符串可以让更长的字符串给另一种类型做消费
#includeiostream
#includealgorithm
#includestring
#includecstring
#includevector
#includemap
#includequeue
using namespace std;
#define int long long
const int N 1e6 10;
pairint, int p[N];
typedef pairint, 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 cd){coutNO\n;return ;}int n s.size();vectorint sa,sb;int i 0;int cnt 0;while(i n){int j i 1;while(j ns[j] ! s[j-1]){j;}int len j - i;if(len 1){i j;continue;}if(len1){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
