Linguistics
算法本质
思维
题目大意
玩家手中有4种不同的字符串特定个数：a b ab ba
题目会给出s，输出玩家能否恰好使用完手中的字符串，将其组合成s。
思路推演
稍加模拟可以发现，因为不存在某个字符串有连续的a或b，所以可以将s分开成若干组，每组不得有连续a或b。
这样情况就缩小至4种了：
偶数长度（分别考虑
a打头和b打头）以
abababab为例，其中一种情况自然是使用4个ab搞定。
思考如果使用了ba的情况，则可以视作a + b + 3个通用，这里的通用指的是ab或ba，没有限制奇数长度（分别考虑
a打头和b打头）以
abababa为例，肯定需要一个离散的a，剩下部分用3个通用即可
还有一点需要思考的是，偶数长度的组，到底应该使用哪种情况。
这里贪心的想，离散的a b优先级是最高的，我们希望ababab最好使用3个ab，当然这里有多个组，但是每个组选择另一种情况都是消耗相同的一对离散a b。
所以我们将这些组按长度排序，尽可能满足长度小的组（这样尽可能减少a b的使用）
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
map<string, int> mp, cod;
vector<int> ab, ba;
cin>>mp["a"]>>mp["b"]>>mp["ab"]>>mp["ba"]; // 记录玩家手中的字符串
string s;
cin>>s;
auto f = [&](int l, int r) {
int len=r-l+1;
if (len%2)
{
cod["tong"] += len/2; // 使用ab ba a+b
if (s[l]=='A')
cod["a"]++; // 使用离散a
else
cod["b"]++; // 使用离散b
}
else
{
if (s[l]=='A')
ab.push_back(len/2); // 需要用len/2个ab 或者 a+b+(len/2-1)个通用
else
ba.push_back(len/2); // 同理
}
};
for (int l=0, r; l<s.length(); l=r+1) // 分组
{
r=l;
while (r<s.length()-1 && s[r]!=s[r+1])
r++;
f(l, r);
}
flag = 1;
sort(ab.begin(), ab.end());
reverse(ab.begin(), ab.end());
sort(ba.begin(), ba.end());
reverse(ba.begin(), ba.end()); // 长度小的组放后边
// 先考虑离散的 a b
mp["a"] -= cod["a"];
mp["b"] -= cod["b"];
if (mp["a"]<0 || mp["b"]<0 || mp["a"]!=mp["b"])
flag = 0;
int cnt = mp["a"]; // a+b数目
while (ab.size() && mp["ab"]>=ab.back()) // 优先使用原生ab
{
mp["ab"] -= ab.back();
ab.pop_back();
}
while (ba.size() && mp["ba"]>=ba.back()) // 优先使用原生ba
{
mp["ba"] -= ba.back();
ba.pop_back();
}
if (cnt < ab.size() + ba.size()) // 有ab.size() + ba.size()实在需要离散对 a+b
flag = 0;
cnt += mp["ab"] + mp["ba"];
cod["tong"] += accumulate(ab.begin(), ab.end(), 0ll) + accumulate(ba.begin(), ba.end(), 0ll);
if (cnt != cod["tong"]) flag = 0;
cout<<(flag ? "YES" : "NO")<<endl;
return;
}Bring Balance
算法本质
思维
题目大意
给定长度2n的括号序列，其中有n个左括号、n个右括号。
玩家希望最后的括号序列合法，可以执行以下操作：
- 选择区间
l r，执行s.reverse(l, r)
输出最小化的操作次数。
思路推演
括号序列的合法，这类题目使用前缀和数组来看待是最好的。
玩家的目的是使得前缀和数组都>=0。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)