526互联

CF1898 E Sofia and Strings 题解

发布时间 2023-11-22 17:01:59作者: Martian148

Link

CF1898 E Sofia and Strings

Question

给出两个由小写字母组成的序列 \(t\) ，\(s\) 我们有两种操作，

  • 删去 \(t\) 中的任意一个字母 \(t_i\)

  • 把 \(t\) 的任意一个区间 \(t_l\sim t_r\) 按从小到大排序

可以操作任意次，问能否把 \(t\) 变成 \(s\)

Solve

先看排序操作，因为操作可以执行任意次，所以我们可以只用区间为二的排序，因为排序的本质就是比较+交换，而区间为二的排序就能做到这一点

对于 \(s\) 上的一个字母 \(s_i\) 我们需要找到 \(t\) 上的一个 \(t_{pos}\) 与 \(s_i\) 配对，贪心的想法，\(t_{pos}\) 越前面越好，在 \(t\) 中，下标小于 \(pos\) 的，字母 \(c\)

  • 如果 \(c>t_{pos}\) 那么可以通过多次交换把 \(c\) 换到 \(t_{pos}\) 后面去
  • 如果 \(c<t_{pos}\) 那么我们想要使用 \(t_{pos}\) 就必须把 \(c\) 删除

如何实现？其实我也想了很久

用 26 个队列记录每个字母出现的位置

对于小于 \(s_i\) 的字母，把所有小于 \(pos\) 的位置都出队列就可以实现了

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
char s1[maxn],s2[maxn];
inline int solve(){
    int len_s1,len_s2;
    scanf("%d%d\n",&len_s1,&len_s2);
    scanf("%s%s",s1+1,s2+1);
    queue<int> mp[26];
    for(int i=1;i<=len_s1;i++) 
    mp[s1[i]-'a'].push(i);
    for(int i=1;i<=len_s2;++i){
        int now=s2[i]-'a';
        if(mp[now].empty()) {return 0;}
        int pos=mp[now].front();mp[now].pop();
        for(int j=0;j<now;++j){
            while(!mp[j].empty() && mp[j].front()<pos) 
                mp[j].pop();
        }
    }
    return 1;
}
int main(){
    // freopen("E.in","r",stdin);
    int T;cin>>T;
    while(T--) 
        printf("%s\n",solve()?"YES":"NO");
    return 0;
}