当前位置：首页 > article >正文

Educational Codeforces Round 174 (Rated for Div. 2) E. A, B, AB and BA

article 2025/2/22 9:23:23

Educational Codeforces Round 174 (Rated for Div. 2) E. A, B, AB and BA

### 题目理解

我们有一个由字符 A 和 B 组成的字符串 s。我们的任务是将这个字符串分割成若干块，每块的长度为 1 或 2。分割后的块只能是以下几种类型：

A
B
AB
BA

并且每种类型的块的数量不能超过给定的限制：

A 的数量不超过 a
B 的数量不超过 b
AB 的数量不超过 ab
BA 的数量不超过 ba

此外，AA 和 BB 这两种块是不允许的。每个字符必须恰好属于一个块。

解题思路

分割字符串：
- 我们可以将字符串 s 分割成两种类型的子串：
  - 连续相同字符的子串（如 AAAA 或 BBBB）。

尽可能长的交替字符的子串（如 ABAB 或 BABA）。

处理连续相同字符的子串：
- 对于连续相同字符的子串，我们可以直接将其分割成若干个 A 或 B 的块。

例如，AAAA 可以分割成 4 个 A 块。

处理交替字符的子串：
- 对于交替字符的子串，我们需要考虑如何用 AB 和 BA 来覆盖它们。
- 例如，ABABAB 可以分割成 3 个 AB 块，或者 2 个 AB 块和 1 个 BA 块。
覆盖交替子串的策略：
- 对于每个交替子串，我们可以用以下方式覆盖：
  - 如果子串以 A 开头且以 A 结尾（如 ABABA），我们可以用 AB 和 BA 来覆盖，但需要额外消耗一个 A。
  - 如果子串以 B 开头且以 B 结尾（如 BABAB），我们可以用 AB 和 BA 来覆盖，但需要额外消耗一个 B。
  - 如果子串以 A 开头且以 B 结尾（如 ABAB），我们可以直接用 AB 来覆盖，或者消耗A,B,然后随意用AB,BA覆盖。
  - 如果子串以 B 开头且以 A 结尾（如 BABA），我们可以直接用 BA 来覆盖，或者消耗A,B,然后随意用AB,BA覆盖。。
贪心策略：
- 我们优先使用 AB 和 BA 来覆盖交替子串，因为这样可以减少对 A 和 B 的消耗。
- 如果 AB 和 BA 的数量不足以覆盖所有交替子串，我们可以通过消耗 A 和 B 来补充。
  
  贪心策略详解
  
  在本题中，贪心策略的核心思想是优先使用最有效的覆盖方式，以减少对 A 和 B 的消耗。具体来说，我们希望通过尽可能多地使用 AB 和 BA 来覆盖交替字符的子串，因为这样可以减少对单个 A 和 B 的需求。
  
  1. 交替子串的分类
  对于每个交替字符的子串，我们可以根据其开头和结尾的字符类型将其分为以下四种情况：
  - 类型 1：以 A 开头且以 A 结尾（如 ABABA）。
  - 类型 2：以 A 开头且以 B 结尾（如 ABAB）。
  - 类型 3：以 B 开头且以 B 结尾（如 BABAB）。
  - 类型 4：以 B 开头且以 A 结尾（如 BABA）。
  2. 覆盖策略
  
  我们的目标是尽可能多地使用 AB 和 BA 来覆盖交替子串，因为这样可以减少对 A 和 B 的消耗。具体策略如下：
  - 优先覆盖可以直接用 AB 或 BA 覆盖的子串（类型 2 和类型 4）。
  - 对于需要用 AB 和 BA 覆盖且需要额外消耗 A 或 B 的子串（类型 1 和类型 3），我们尽量通过消耗 A 和 B 来补充。
  3. 排序思想
  
  为了最大化利用 AB 和 BA，我们需要对交替子串进行排序。排序的依据是：
  - 优先覆盖可以直接用 AB 或 BA 覆盖的子串（即类型 2 和类型 4）。
  - 对于需要用 AB 和 BA 覆盖且需要额外消耗 A 或 B 的子串（类型 1 和类型 3），我们按子串长度从小到大排序，这样可以优先处理较短的子串，减少对 A 和 B 的消耗。
  在代码中，我们使用了一个三元组 {开头字符类型, 长度/2, 是否可以用 AB 和 BA 覆盖} 来表示每个交替子串，并通过自定义的比较函数 cmp 来实现排序。
  
  4. 贪心覆盖
  
  在排序后，我们按照以下步骤进行覆盖：
  1. 直接覆盖：
    - 对于可以直接用 AB 或 BA 覆盖的子串（类型 2 和类型 4），直接使用 AB 或 BA 来覆盖。
  2. 补充覆盖：
    - 对于需要用 AB 和 BA 覆盖且需要额外消耗 A 或 B 的子串（类型 1 和类型 3），我们尽量通过消耗 A 和 B 来补充。
    - 如果 AB 和 BA 的数量不足以覆盖所有子串，则通过消耗 A 和 B 来补充。
  3. 判断是否可行：
    - 如果所有子串都能被覆盖，则输出 YES，否则输出 NO。
  代码中的排序实现
  
  在代码中，我们使用了一个三元组 {开头字符类型, 长度/2, 是否可以用 AB 和 BA 覆盖} 来表示每个交替子串，并通过自定义的比较函数 cmp 来实现排序：
```
bool cmp(array<int, 3> a, array<int, 3> b) {
    if (a[2] == b[2])
        return a[1] < b[1]; // 按长度从小到大排序
    else
        return a[2] < b[2]; // 优先处理可以直接用 AB 或 BA 覆盖的子串
}
```
  排序后，我们按照以下顺序处理交替子串：
  1. 优先处理可以直接用 AB 或 BA 覆盖的子串。
  2. 对于需要用 AB 和 BA 覆盖且需要额外消耗 A 或 B 的子串，按长度从小到大处理。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define Paddi ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

vector<string> s1; // 存储连续相同字符的子串
vector<string> s2; // 存储交替字符的子串

// 比较函数，用于排序
bool cmp(array<int, 3> a, array<int, 3> b) {
    if (a[2] == b[2])
        return a[1] < b[1];
    else
        return a[2] < b[2];
}

// 分割字符串
void spilt(string s) {
    int flag = 0, left = 0;
    if (s[0] == s[1])
        flag = 1; // 连续相同字符
    else
        flag = 2; // 交替字符
    for (int i = 1; i < s.size() - 1; i++) {
        if (flag == 1) {
            if (s[i] != s[i + 1])
                s1.push_back(s.substr(left, (i - 1 - left + 1))), flag = 2, left = i;
        } else if (flag == 2) {
            if (s[i] == s[i + 1])
                s2.push_back(s.substr(left, i - left + 1)), flag = 1, left = i + 1;
        }
    }
    if (left == s.size() - 1)
        s1.push_back(s.substr(s.size() - 1, 1));
    else {
        if (flag == 1)
            s1.push_back(s.substr(left, s.size() - left));
        else
            s2.push_back(s.substr(left, s.size() - left));
    }
}

signed main() {
    Paddi;
    int T;
    cin >> T;
    while (T--) {
        s1.clear(), s2.clear();
        string s;
        cin >> s;
        spilt(s);
        map<string, int> rec;
        cin >> rec["A"] >> rec["B"] >> rec["AB"] >> rec["BA"];
        if (s.size() == 1) {
            if (((s[0] == 'A') and rec["A"]) or ((s[0] == 'B') and rec["B"]))
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
            continue;
        }
        for (auto i : s1) {
            if (i[0] == 'A')
                rec["A"] -= i.size();
            else if (i[0] == 'B')
                rec["B"] -= i.size();
        }
        array<int, 4> r;
        vector<array<int, 3>> s3;
        for (auto i : s2) {
            if (i[0] == i.back() and i[0] == 'A') {
                rec["A"]--;
                array<int, 3> now = {0, i.size() / 2, 1};
                s3.push_back(now);
            } else if (i[0] != i.back() and i[0] == 'A') {
                array<int, 3> now = {0, i.size() / 2, 0};
                s3.push_back(now);
            } else if (i[0] == i.back() and i[0] == 'B') {
                rec["B"]--;
                array<int, 3> now = {1, i.size() / 2, 1};
                s3.push_back(now);
            } else if (i[0] != i.back() and i[0] == 'B') {
                array<int, 3> now = {1, i.size() / 2, 0};
                s3.push_back(now);
            }
        }
        if (rec["A"] < 0 or rec["B"] < 0)
            cout << "NO" << endl;
        else {
            int k = min(rec["A"], rec["B"]);
            int sum = 0;
            for (auto i : s3)
                sum += i[1];
            if (sum > (rec["AB"] + rec["BA"] + k))
                cout << "NO" << endl;
            else {
                bool ok = true;
                int sum2 = 0;
                sort(s3.begin(), s3.end(), cmp);
                for (auto i : s3) {
                    if (i[2] == 1)
                        sum2 += i[1];
                    else {
                        if (i[0] == 0) {
                            if (rec["AB"] >= i[1])
                                rec["AB"] -= i[1];
                            else {
                                if (k)
                                    k--, i[1]--, sum2 += i[1];
                                else
                                    ok = false;
                            }
                        } else if (i[0] == 1) {
                            if (rec["BA"] >= i[1])
                                rec["BA"] -= i[1];
                            else {
                                if (k)
                                    k--, i[1]--, sum2 += i[1];
                                else
                                    ok = false;
                            }
                        }
                    }
                }
                if (ok) {
                    sum2 -= (rec["AB"] + rec["BA"] + k);
                    if (sum2 <= 0)
                        cout << "YES" << endl;
                    else
                        cout << "NO" << endl;
                } else
                    cout << "NO" << endl;
            }
        }
    }
    return 0;
}

代码解释

分割字符串：
- spilt 函数将字符串 s 分割成连续相同字符的子串和交替字符的子串，并分别存储在 s1 和 s2 中。
处理连续相同字符的子串：
- 对于每个连续相同字符的子串，直接消耗 A 或 B 的数量。
处理交替字符的子串：
- 对于每个交替字符的子串，根据其开头和结尾的字符类型，生成一个三元组 {开头字符类型, 长度/2, 是否可以用 AB 和 BA 覆盖}。
贪心策略：
- 优先使用 AB 和 BA 来覆盖交替子串。
- 如果 AB 和 BA 的数量不足，则通过消耗 A 和 B 来补充。
判断是否可行：
- 如果所有子串都能被覆盖，则输出 YES，否则输出 NO。