D. Slavic's Exam - 题解

比赛与标签

比赛: Codeforces Round 964 (Div. 4) 标签: greedy, implementation, strings 难度: *1100

题目大意喵~

主人你好呀，是聪明的猫娘我哦~ 喵~ 这道题其实是在考验我们的细心和策略呢！

题目是这样的：我们有两个字符串，一个叫做 s，另一个叫做 t。

字符串 s 里面可能包含小写字母和一些问号 ?。
字符串 t 只包含小写字母。

我们的任务是，把 s 里面的每一个 ? 都换成一个小写字母，使得 t 能够成为 s 的一个子序列。

子序列是什么意思呐？ 比如说，"ace" 就是 "abcde" 的子序列，因为我们可以从 "abcde" 中删掉 'b' 和 'd' 得到 "ace"，字符的相对顺序没有变。但是 "cae" 就不是哦，因为 'c' 和 'a' 的顺序反了。

如果我们可以完成这个任务，就要先输出 "YES"，然后输出修改后的字符串 s。如果不管怎么换 ? 都做不到，那就只能伤心地输出 "NO" 啦。

猫娘的贪心小爪子🐾

呐，要让 t 成为 s 的子序列，最直接的想法就是从头开始一个一个地匹配呀！这种“能匹配就立刻匹配”的思路，就是我们常说的贪心策略哦！

我们可以用两根小指头...啊不，是两个指针来解决这个问题！

一个指针 i，指向 s 的当前位置。
另一个指针 j，指向 t 中我们当前需要匹配的字符位置。

我们的目标是，在 s 中按顺序找到 t[0], t[1], t[2], ... 直到 t 的最后一个字符。

现在，我们让指针 i 从 s 的开头走到结尾，看看会发生什么吧：

当 s[i] 和 t[j] 恰好相等时：太棒啦！我们找到了 t 中需要的第 j 个字符！这时候，我们就可以心满意足地把两个指针都向后移动一位（i++, j++），接着去为 t 的下一个字符寻找归宿啦。
当 s[i] 是一个万能的 ? 时：喵~ 这是一个绝佳的机会！既然我们当前正需要匹配 t[j]，那最贪心的做法就是毫不犹豫地把这个 ? 变成 t[j]。这样一来，匹配就成功了！和第一种情况一样，我们把两个指针都向后移动（i++, j++）。
当 s[i] 和 t[j] 不相等，并且 s[i] 也不是 ? 时：呜... s 的这个位置上的字符 s[i] 帮不了我们。但是没关系，子序列不要求连续，我们可以在 s 的后面继续寻找 t[j]。所以，我们只把 s 的指针 i 向后移动（i++），而 t 的指针 j 保持不动，继续等待它的真命天子出现。

我们一直重复这个过程，直到 i 走完整个 s 字符串。

最后怎么判断成功还是失败呢？

成功：如果在 s 还没走完的时候，我们的 j 指针就已经走到了 t 字符串的末尾（也就是 j 等于 t 的长度 m），这说明 t 的所有字符都按顺序在 s 中找到了位置！任务成功！耶！🎉
失败：如果 i 已经走完了整个 s，但是 j 还没走完 t，那就说明我们没能找到 t 的全部字符，任务失败了... 呜...

别忘了收尾工作哦！ 如果成功了，s 里面可能还有一些我们没用到的 ?。这些 ? 已经不影响大局了，随便把它们变成任何字母都可以，比如 'a'，这样最简单啦。

代码实现，开始Coding喵！

cpp

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

// 使用 using namespace std; 可以让代码更简洁，但在大项目中要小心命名冲突哦~
using namespace std;

int main() {
    // 开启高速 I/O，让程序跑得快一点点
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T; // 读取测试用例的数量
    vector<string> ans; // 用一个 vector 来存储所有答案，最后一起输出，效率更高喵

    while (T--) {
        string s, t;
        cin >> s >> t;
        int n = s.size();
        int m = t.size();

        // i 是 s 的指针，j 是 t 的指针，喵~
        int i = 0, j = 0;

        // 当两个指针都没有越界时，进行匹配
        while (i < n && j < m) {
            // Case 1 & 2: s[i] 和 t[j] 匹配，或者 s[i] 是万能的 '?'
            if (s[i] == t[j] || s[i] == '?') {
                // 如果是 '?'，就贪心地把它变成我们需要的 t[j]
                if (s[i] == '?') {
                    s[i] = t[j];
                }
                // 匹配成功！两个指针都向前走一步
                i++;
                j++;
            } else {
                // Case 3: s[i] 没用上，只能跳过它，继续在 s 中寻找 t[j]
                i++;
            }
        }

        // 如果 j 走完了 t，说明 t 的所有字符都按顺序找到了，任务成功！
        if (j == m) {
            // 把剩下的 '?' 随便填个 'a' 就好啦，它们不影响结果
            for (char &c : s) {
                if (c == '?') {
                    c = 'a';
                }
            }
            ans.push_back("YES");
            ans.push_back(s);
        } else {
            // 否则就是失败了... 呜...
            ans.push_back("NO");
        }
    }

    // 最后统一输出所有测试用例的答案
    for (int idx = 0; idx < ans.size(); idx++) {
        cout << ans[idx] << '\n';
    }

    return 0;
}

复杂度分析

时间复杂度: O(|s|) 的说。我们的核心逻辑是一个 while 循环，其中指针 i 单调递增，最多遍历一次字符串 s。之后填充剩余 ? 的循环也最多遍历一次 s。所以总的时间复杂度和 s 的长度是线性关系。
空间复杂度: O(|s|) 的说。我们需要存储修改后的字符串 s，这本身就需要 O(|s|) 的空间。另外，我们用 vector 存储所有答案，在最坏情况下，其总大小与所有测试用例的 |s| 之和成正比。

猫娘的智慧总结 ✨

这道题完美地展示了贪心思想和双指针技巧的结合，这是解决字符串子序列问题的经典方法哦！

核心思想：贪心。对于 t 中的每一个字符，我们都用 s 中最靠前的、能匹配上的位置去满足它。这个策略是正确的，因为早点满足当前需求，可以为后续的字符留下更多的选择空间，绝对不会让情况变得更糟。
双指针：一个指针追踪主串 s 的进度，一个指针追踪子序列串 t 的需求。这种模式非常高效，一定要掌握呀！
? 的处理：把 ? 看作是一个可以被我们利用的宝贵资源。当我们需要它时，就毫不犹豫地使用它，这就是贪心的精髓所在。

希望这篇题解能帮助到主人哦！如果还有其他问题，随时可以再来找猫娘玩！喵~ ❤️

D. Slavic's Exam - 题解 ​

比赛与标签 ​

题目大意喵~ ​

猫娘的贪心小爪子🐾 ​

代码实现，开始Coding喵！ ​

复杂度分析 ​

猫娘的智慧总结 ✨ ​