D. Deletive Editing - 题解

比赛与标签

比赛: 2021-2022 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) 标签: greedy, *900 难度: *900

题目大意喵~

这道题描述了一个叫做 "删除编辑" (Deletive Editing) 的文字游戏，规则是这样的呐：

我们有一个初始字符串 s 和一个目标字符串 t。
我们可以进行任意次操作。每次操作，我们会喊出一个字母，然后从当前的字符串中删除 第一个 出现的该字母。
问题是：我们是否能通过一系列这样的操作，将初始字符串 s 变成目标字符串 t 呢？

比如说，s = "DETERMINED"，我们想得到 t = "TERM"。如果我们喊出 'D'，s 变成 "ETERMINED"。再喊出 'E'，s 变成 "TERMINED"。再喊出 'R'，s 变成 "TEMINED"。再喊出 'M'，s 变成 "TEINED"。啊哦，我们需要的 'R' 和 'M' 都在，但是顺序好像不对劲了，而且我们好像没办法只留下我们想要的那个 'E' 呢。

所以，我们的任务就是判断，给定的 s 和 t，是否存在一种删除顺序，使得 s 最终能变成 t。

解题思路的奇妙之旅~

嘿嘿，这个问题最关键的地方就在于“删除第一个出现的字母”这个规则。这给了我们一个非常重要的限制，也恰恰是解题的突破口哦！

让我们来仔细想想，如果我们想保留 s 中的某个字符，那么所有在它前面的、我们不想要的字符都必须被删除掉。特别是，如果 s 中有多个相同的字符，比如 s = "ABCA"，我们想保留第二个 'A'，那么第一个 'A' 就必须被删除掉。

正向思考（从前往后）似乎有点复杂，因为我们每一步的选择都会影响后续的可能性。那……不如我们换个方向，从后往前思考一下？这种逆向思维在算法题里可是很强大的魔法喵！

假设目标字符串是 t = t_1 t_2 ... t_k。我们来考虑 t 的最后一个字符 t_k。这个 t_k 必须是 s 中保留下来的一个字符。那么，它应该对应 s 中的哪一个 t_k 字符呢？

答案是：它必须对应 s 中最后一次出现的那个 t_k 字符！

为什么呢？喵~ 听我解释！假如 s 中有多个 t_k，比如 s = "...(t_k)_i...(t_k)_j..."，其中 i < j。如果我们选择保留第 i 个位置的 t_k，那么第 j 个位置的 t_k 就会留在字符串里，并且在我们的目标字符之后。我们没办法在不删除第 i 个 t_k 的情况下删除第 j 个 t_k，因为删除操作总是针对第一个出现的！所以，为了能成功构造 t，我们只能保留那个最“安全”的、也就是最后出现的 t_k。

想通了这一点，一个绝妙的贪心策略就诞生啦！

我们要找 t 的最后一个字符 t_k，它必须对应 s 中最后一个出现的 t_k。
接着，我们要找 t 的倒数第二个字符 t_{k-1}，它必须对应在刚刚找到的 t_k 之前的子串中，最后一个出现的 t_{k-1}。
以此类推，直到我们为 t 的所有字符都在 s 中找到了对应的位置。

这个过程听起来是不是有点像从后往前匹配？完全正确！我们可以这样做：

我们从右到左遍历目标字符串 t。
同时，我们也从右到左遍历初始字符串 s。
当我们在 s 中找到一个字符，它恰好是当前 t 中正在寻找的字符时，我们就认为它们匹配上了，然后继续在 t 中寻找前一个字符。

举个例子：s = "DETERMINED", t = "TRME"

我们想找 t 的最后一个字符 'E'。我们从 s 的末尾开始扫描。 DETERMIN**E**D -> 找到了！这个 'E' 就是我们要的。我们把它记下来。现在我们要在 s 的 "DETERMIN" 部分找 'M'。
我们想找 'M'。继续从刚才 'E' 的位置往前扫描 s。 DETER**M**IN -> 找到了！记下 'M'。现在要在 s 的 "DETER" 部分找 'R'。
我们想找 'R'。继续扫描。 DETE**R** -> 找到了！记下 'R'。现在要在 s 的 "DETE" 部分找 'T'。
我们想找 'T'。继续扫描。 DE**T**E -> 找到了！记下 'T'。
我们从 s 中依次找到了 'E', 'M', 'R', 'T'。把这个顺序反过来，就是 "TRME"，和我们的目标 t 完全一样！所以答案是 "YES"！

代码实现上，我们可以用一个计数器或者频率数组来充当我们的“购物清单”，这样会更方便哦！

代码实现喵~

下面就是实现这个美妙思路的AC代码啦！Mya 已经为你们加上了详细的注释，快来看看吧！

cpp

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

using namespace std;

int main() {
    // 开启高速输入输出，让程序跑得飞快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n; // 读取测试用例的数量
    while (n--) {
        string s, t;
        cin >> s >> t; // 读取初始字符串s和目标字符串t

        // 喵~ 先做一个快速检查！
        // 如果目标t需要的某个字符数量比s中总共有的还多，那肯定不可能啦！
        vector<int> freq_t(26, 0); // 统计t中每个字符的频率
        for (char c : t) {
            freq_t[c - 'A']++;
        }
        vector<int> freq_s(26, 0); // 统计s中每个字符的频率
        for (char c : s) {
            freq_s[c - 'A']++;
        }

        bool possible = true;
        for (int i = 0; i < 26; i++) {
            if (freq_t[i] > freq_s[i]) {
                possible = false;
                break;
            }
        }

        if (!possible) {
            cout << "NO\n";
            continue; // 直接处理下一个测试用例
        }

        // 这是核心的贪心策略实现~
        // 我们从s的末尾开始向前遍历
        string new_s = ""; // 用来构建我们从s中选出的子序列
        
        // freq_t在这里被巧妙地用作一个“待办清单”或“购物清单”
        // 记录我们还需要为t找到哪些字符
        for (int i = s.size() - 1; i >= 0; i--) {
            char c = s[i];
            // 如果当前字符c是我们“购物清单”上需要的
            if (freq_t[c - 'A'] > 0) {
                freq_t[c - 'A']--; // 找到了一个，清单上的需求量减一
                new_s += c;        // 把这个字符加入我们构建的字符串
            }
        }

        // 因为我们是从后往前找的，所以构建出的new_s是t的逆序
        // 所以需要把它反转过来
        reverse(new_s.begin(), new_s.end());

        // 最后，检查我们贪心构造出的子序列是否就是目标t
        if (new_s == t) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(|s| + |t|) 的说。我们首先需要遍历 s 和 t 各一次来统计字符频率，这部分是 O(|s| + |t|)。然后，我们从后往前遍历 s 一次，这是 O(|s|)。最后反转和比较字符串，最多是 O(|t|)。所以总的时间复杂度是线性的，非常高效！
空间复杂度: O(|t|) 的说。我们用了两个频率数组，大小是固定的26，所以是 O(1)。我们还用了一个 new_s 字符串来存储结果，它的最大长度是 |t|。所以空间复杂度主要由 new_s 决定，是 O(|t|)。

知识点与总结~

这道题真是太棒了，它教会了我们一个非常重要的思想，喵~

逆向思维: 当正向思考陷入困境时，不妨试试从结果倒推回去。很多看似复杂的问题，在逆向视角下会变得豁然开朗！
贪心策略: 本题的核心是找到了一个局部最优解能导向全局最优解的策略——总是选择最后出现的那个字符。理解并证明这个贪心选择的正确性是解题的关键。
巧用数据结构: 使用频率数组作为“待办清单”来跟踪还需要匹配的字符，这是一个非常优雅和高效的实现技巧，避免了复杂的指针操作。

总而言之，只要抓住了“删除第一个”这个核心规则，并勇敢地采用逆向思维，问题就迎刃而解啦！希望大家都能从中学到东西，以后遇到类似的题目也能充满信心地解决！加油喵~！

D. Deletive Editing - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路的奇妙之旅~ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结~ ​