题解：P12817 [NERC 2021] Deletive Editing

___define___ · 2025-06-14 21:07:01 · 题解

题目传送门

思路

由于每次操作只能删除被删除字母的第一次出现，所以考虑翻转单词 s，再查询单词 t 中每一个字母在翻转后的单词 s 中第一次出现的位置，最后判断这些查询结果是否是升序的即可，注意查询顺序应从单词 t 的结尾开始，否则会使程序出现错误。

这里翻转与查询可以使用 STL 库中自带的 reverse 与 find 函数，会使程序更加简洁。

AC Code

#include<bits/stdc++.h>
using namespace std;
int n;
string s1,s2;
int a[105];
signed main(){
    scanf("%d",&n);
    while(n--)
    {
        cin>>s1>>s2;
        reverse(s1.begin(),s1.end());
        bool z=0;
        for(int i=s2.size()-1;i>=0;--i)
        {
            a[i]=s1.find(s2[i]);
            if(a[i]!=-1)s1[a[i]]='0';
            else z=1;
            if(i!=s2.size()-1) 
                if(a[i]<a[i+1]) z=1;
        }
        if(!z) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}