题解：P12817 [NERC 2021] Deletive Editing

P12817 [NERC 2021] Deletive Editing

Daisy 从单词中删除该字母的第一次出现，她是否能够从给定的初始单词出发，通过玩若干轮（包括零轮）这个游戏，最终得到她想要的单词。

• 不在 内的字母可以任意依次删去，此时得到一个只含有想要单词内字母的字符串 。
• 对于 ，唯一的操作是从前向后删去字母，所以找到的结果 一定是在结尾。所以让 逐个末位相比对，匹配的就在 中进行 pop_back 操作，更新当前任务为次末尾字符。
• 如果在从后向前扫描 时，一个在 中出现了的字母却并不在 的末尾，是不合法的。即使前面出现了 ，也会因为当前字符出现在后面无法删除。

用题干中的例子：deTeRMinEd,determinEd，很好理解了。

所以就两点：存在，按序。实现的时候并不会去构造 字符串，只要代入 查找一下即可。

代码如下：

#include<bits/stdc++.h>

using namespace std;

int n;
string s, t, tmp;

inline bool check(string str, char ch) {
    for (char c : str)
        if (c == ch)
            return true;
    return false;
}

int main() {
    scanf("%d", &n);
    while (n--) {
        bool flag = true;
        cin >> s >> t, tmp.clear();
        for (int i = s.size() - 1; i >= 0; --i)
            if (check(t, s[i])) {
                if (t.back() == s[i])
                    t.pop_back();
                else
                    flag = false, i = -1;
            }
        if (flag && t.empty())
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

花絮：qaq 编辑字符串也是 edit。