E. Changing the String - 题解

比赛与标签

比赛: Educational Codeforces Round 179 (Rated for Div. 2) 标签: binary search, data structures, greedy, implementation, sortings, strings 难度: *1900

题目大意喵~

主人你好呀！这道题是说，我们有一根可爱的字符串 s，它只由 'a', 'b', 'c' 这三种小猫爪印组成，喵~ 同时呢，我们还有 q 个魔法指令。

每个指令的形式是 (x, y)，表示我们可以从字符串 s 中挑选一个字符 x，然后把它变成字符 y。当然，我们也可以选择什么都不做，悄悄路过~

我们的任务是，必须按照给定的顺序来考虑这 q 个魔法指令，并做出最棒的选择，使得最终得到的字符串 s 的字典序是最小最小的！也就是说，要让字符串尽可能地靠前，比如多一些 'a' 总是好的说！

解题思路分析喵~

要让字符串的字典序最小，我们的策略当然是越贪心越好啦！就像小猫总是先吃最美味的鱼干一样，我们也要优先处理字符串最前面的字符，让它们变得尽可能小，喵~

所以，一个非常自然的贪心思路就出现啦：我们从左到右遍历字符串 s 的每一个位置 i，想尽一切办法让 s[i] 这个字符变得最小。

我们的目标顺序是 a > b > c。

对于第 i 个位置的字符 s[i]：

1. 如果 s[i] 已经是 'a' 了： 耶！它已经是最小的字符了，我们不需要为它消耗任何魔法指令。直接开心地跳到下一个位置就好啦，喵~

2. 如果 s[i] 是 'b'： 我们的目标是把它变成 'a'。

   • 直接变身 (b -> a)：最简单的方法是直接使用一个 b -> a 的魔法指令。我们有很多指令，但它们有顺序要求。所以，我们应该使用最早的、还没被用过的 b -> a 指令。
   • 曲折变身 (b -> c -> a)：如果直接变身的路不通（没有可用的 b -> a 指令），我们是不是就放弃了呢？不！我们还可以迂回一下！我们可以先用一个 b -> c 的指令把它变成 'c'，再用一个 c -> a 的指令把它变成 'a'。但这里有个关键点：b -> c 指令的执行顺序必须在 c -> a 指令之前！
   • 选择哪条路呢？ b -> a 只需要一个指令，而 b -> c -> a 需要两个。我们应该优先考虑更简单的 b -> a 路径。如果不行，再考虑 b -> c -> a。

3. 如果 s[i] 是 'c'： 这是最需要努力的情况了！我们的首要目标是 'a'，次要目标是 'b'。

   • 目标 'a'：
     • 直接变身 (c -> a)：和上面一样，我们寻找最早可用的 c -> a 指令。
     • 曲折变身 (c -> b -> a)：如果直接变身不行，我们看看能不能先用 c -> b，再用 b -> a。同样，c -> b 的指令顺序必须在 b -> a 之前。
   • 目标 'b' (如果变不成 'a')：
     • 如果我们用尽浑身解数也无法把 s[i] 变成 'a'，那退而求其次，变成 'b' 也是一个不错的选择！这需要一个 c -> b 的指令。

如何管理这些魔法指令呢？

我们需要一个高效的方式来存储每个种类的指令（比如 a->b, b->a 等），并且能快速找到“最早可用”的那个。std::set 这个数据结构就非常适合！它会自动给元素排序。我们可以为每一种 x -> y 的变换都建立一个 set，里面存放这些指令的原始序号（从 0 到 q-1）。

• 找最早的指令：就是 set 的第一个元素 *set.begin()。
• 使用一个指令：就是把它从 set 中移除 set.erase(set.begin())。
• 找在某个指令 op1 之后的最早指令：可以使用 set.lower_bound(op1)，它能帮我们找到第一个不小于 op1 的指令，喵~

结合起来，我们的最终策略就是： 从 i = 0 到 n-1 遍历字符串：

• 对于 s[i] == 'b'：
  1. 优先查找是否有可用的 b -> a 指令。有就用掉，把 s[i] 变成 'a'。
  2. 如果没有，再查找是否存在一个 b -> c 指令 (op1) 和一个在它之后的 c -> a 指令 (op2)。有就用掉，把 s[i] 变成 'a'。
• 对于 s[i] == 'c'：
  1. 优先查找是否有可用的 c -> a 指令。有就用掉，把 s[i] 变成 'a'。
  2. 如果没有，再查找是否存在 c -> b -> a 的指令链。这个在代码里实现得很巧妙：它先尝试使用一个 c -> b 指令，然后立即检查是否存在一个更晚的 b -> a 指令来完成变身。如果能，就一步到位变成 'a'。如果不能，就只完成 c -> b 的变身。
  3. 如果连 c -> b 都不行，那就只好保持 'c' 不变啦。

这样从左到右贪心地处理，就能保证每一步都为获得字典序最小的字符串做出了最优的局部决策，从而得到全局最优解，的说！

代码实现喵~

#include <iostream>
#include <vector>
#include <set>
#include <string>

// 使用 using namespace std; 是为了代码简洁，但在大项目中最好避免哦~
using namespace std;

void solve() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    // v[x][y] 是一个 set，存储了所有 x -> y 转换操作的原始索引
    // 比如 v[0][1] 存储所有 'a' -> 'b' 的操作索引
    vector<vector<set<int>>> v(3, vector<set<int>>(3));
    for (int i = 0; i < q; i++) {
        char x, y;
        cin >> x >> y;
        int xi = x - 'a';
        int yi = y - 'a';
        v[xi][yi].insert(i);
    }

    // 从左到右遍历字符串，进行贪心选择
    for (int i = 0; i < n; i++) {
        // 如果已经是 'a'，就不用管啦，它是最棒的！
        if (s[i] == 'a') 
            continue;
        
        int cur = s[i] - 'a';

        // --- 情况1: 当前字符是 'b' ---
        if (cur == 1) { // s[i] == 'b'
            // 策略1: 直接 b -> a
            if (!v[1][0].empty()) {
                // 使用最早的 b -> a 操作
                v[1][0].erase(v[1][0].begin());
                s[i] = 'a';
            }
            // 策略2: 间接 b -> c -> a
            else if (!v[1][2].empty()) {
                // 找到最早的 b -> c 操作
                int op1 = *v[1][2].begin();
                // 寻找在 op1 之后的最早的 c -> a 操作
                auto it2 = v[2][0].lower_bound(op1);
                if (it2 != v[2][0].end()) {
                    // 如果找到了这样的操作链，就执行它们
                    v[1][2].erase(v[1][2].begin());
                    v[2][0].erase(it2);
                    s[i] = 'a';
                }
            }
        }
        // --- 情况2: 当前字符是 'c' ---
        else if (cur == 2) { // s[i] == 'c'
            // 策略1: 优先尝试直接 c -> a
            if (!v[2][0].empty()) {
                // 使用最早的 c -> a 操作
                v[2][0].erase(v[2][0].begin());
                s[i] = 'a';
            }
            // 策略2: 如果不能直接变 'a', 尝试变成 'b'
            else if (!v[2][1].empty()) {
                // 找到最早的 c -> b 操作
                int op1 = *v[2][1].begin();
                v[2][1].erase(v[2][1].begin());
                s[i] = 'b'; // 先假设我们把它变成了 'b'

                // 策略3: 检查这个 'b' 能不能进一步变成 'a' (即 c -> b -> a)
                auto it2 = v[1][0].lower_bound(op1);
                if (it2 != v[1][0].end()) {
                    // 如果存在一个在 c->b 之后发生的 b->a 操作，太棒了！
                    v[1][0].erase(it2);
                    s[i] = 'a'; // 最终目标达成！
                }
            }
        }
    }
    cout << s << '\n';
}

int main() {
    // 加速输入输出，让程序跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O((n + q) * log q) 的说

  • 首先，我们需要读取 q 个操作并把它们的索引放入 set 中。每次插入 set 的时间是 O(log q)，所以这部分的复杂度是 O(q * log q)。
  • 然后，我们遍历长度为 n 的字符串。在循环的每一步中，我们最多进行常数次 set 的操作（如 begin, erase, lower_bound）。这些操作的复杂度都是 O(log q)，因为 set 的大小最多是 q。所以主循环的复杂度是 O(n * log q)。
  • 把它们加起来，总的时间复杂度就是 O(q * log q + n * log q) = O((n + q) * log q)。对于这道题的数据范围来说，是完全可以接受的呐！

• 空间复杂度: O(n + q) 的说

  • 我们需要存储长度为 n 的字符串 s，这需要 O(n) 的空间。
  • 我们的 v 数组里面有很多 set，它们总共存储了 q 个操作的索引，所以这部分需要 O(q) 的空间。
  • 所以总的空间复杂度就是 O(n + q) 啦。

知识点与总结喵~

这道题真是一次愉快的思维体操呢！它教会了我们几件重要的事情：

1. 贪心大法好：面对要求字典序最小的问题，从左到右的贪心策略通常是正解。因为前面的字符对字典序的影响是决定性的！
2. 选择对的数据结构：为了高效地管理和查询这些带顺序的魔法指令，std::set 是我们的不二之选。它提供的 lower_bound 功能在处理“某个操作之后”这类约束时特别有用，这其实就是 binary search 标签的由来哦。
3. 思路要全面：不能只想着一步到位的操作（比如 b -> a），还要考虑像 c -> b -> a 这样的“组合技”。把所有可能变优的路径都考虑到，才能得到真正的最优解。
4. 代码实现要优雅：代码中处理 s[i] == 'c' 的逻辑非常巧妙，它把“变成b”和“通过b变成a”两种可能融合在了一起，值得我们学习喵！

只要思路清晰，一步一步来，再复杂的问题也能被我们解决的喵！加油哦，主人！