CF1898E Sofia and Strings

2024-03-13

Solution

551 Words

题目大意

给定两种对字符串的操作:

删除字符串第 $i$ 位的字符。
选择 $[l, r]$, 将 $s_{[l, r]}$ 的字符串按字典序排序。

现在有长为 $n, m$ 的字符串 $s, t$, 问是否能通过这两种操作把 $s$ 变成 $t$。

多组数据 $, 1 \leq n, m, \sum n, \sum m\leq 2 \times 10^5, 1 \leq t \leq 10 ^ 4$

题目分析

首先忽略顺序限制，认为 $t$ 是 $s$ 重排后的字符串 $s’$ 的子序列。

回顾子序列的求法，我们对 $s$ 中的 $26$ 种字符分别维护了一个队列，存储每种字符出现的位置。对于每个 $t_i$，我们寻找第 $i$ 个字符最近的一个出现位置。如果每个 $t_i$ 都能找到对应，那么子序列匹配成功。

现在考虑如何在引入操作 $2$ 的情况下修改这一算法。假设对于 $1 \dots i - 1$ 均已重排完毕。对于 $t_i$，我们同样寻找第 $i$ 个字符最近的一个出现位置，设为 $j$。则我们需要删除 $s_{i \dots j}$ 中所有小于 $t_i$ 的字符，并重排。如果我们能对整个 $t$ 执行这一过程，那么答案为是，否则为否。容易证明这样贪心是最优的。

注意到我们并不需要显式维护 $s$ 的删除，只需要在记录 $26$ 种字符出现位置的队列中弹出无效位置即可。

时间复杂度 $O(26(n + m))$

代码

#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
#define meow(cat...) fprintf(stderr, cat)

const int MaxN = 2e5 + 10;

int n, m;
std::queue<int> q[26];
char s[MaxN], t[MaxN];

inline int read()
{
    int x = 0;
    char ch = getchar();
    while(ch > '9' || ch < '0')
        ch = getchar();
    while(ch <= '9' && ch >= '0') 
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}

signed main()
{   
    int T = read();
    while(T--)
    {
        int flag = 1;
        scanf("%d%d%s%s", &n, &m, s + 1, t + 1);
        for(int i = 0; i < 26; i++)
            while(!q[i].empty()) q[i].pop();
        for(int i = 1; i <= n; i++)
            q[s[i] - 'a'].push(i);
        for(int i = 1; i <= m; i++)
        {
            int c = t[i] - 'a';
            if(q[c].empty())
                { flag = 0; break; }
            int j = q[c].front();
            q[c].pop();
            for(int v = 0; v < c; v++)
                while(!q[v].empty() && q[v].front() < j)
                    q[v].pop();
        }
        puts(flag ? "Yes" : "No");
    }
    return 0;
}

字符串, 贪心

CF1898E Sofia and Strings

题目大意

题目分析

代码

目录

分类

Your browser is out-of-date!