Jingye Qiu

Jingye Qiu

he/him

Student at Hunan University

题解 - CodeForces 1898E Sofia and Strings

1 minute read

Published:

题目传送门

分析

注意到：对某个长度为 \(n\) 的子串进行排序操作，可以拆分成若干次对长度为 \(2\) 的子串排序的操作。具体地，对于子串 \(s_is_{i+1}\)，如果 \(s_i>s_{i+1}\)，调换两者顺序；否则不进行任何操作。所以，不妨化繁为简，每次只对长度为 \(2\) 的子串考虑排序操作。

基于上面的思考，若能构造出目标字符串，目标字符串中的每个元素 \(t_i\)，要么是在原地没有因为排序移动过，要么被比它小的字符调换到右边，要么被比它大的字符调换到左边。形式化地，记 \(t_i\) 在 \(s\) 中的原始下标为 \(now_i\)，那么对于所有满足 \(t_j<t_i\) 且 \(j>i\) 的 \(j\)，有 \(now_j>now_i\)，对于所有满足 \(t_j>t_i\) 且 \(j<i\) 的 \(j\)，有 \(now_j<now_i\)。

不妨考虑贪心，从小到大循环 \(26\) 个小写字母，从右往左填入当前循环的字母，记录 \(now\) 在当前位置的后缀最小值 \(mi\)，最大化当前位置的 \(now_i\)，使得 \(now_i< mi\)。如果不存在这样的 \(now_i\)，则无法构造目标字符串。具体实现时可以分别预先记录每个字母在原字符串、目标字符串中的位置，方便填入。时间复杂度接近 \(O(\alpha\cdot m)\)，本题 \(\alpha=26\)。

C++实现

// C++11 or later
#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int N = 2e5 + 10;
int n, m, now[N];
char given[N], target[N];
// v1记录每个字母在原字符串中的位置，v2记录每个字母在目标字符串中的位置
vector<int> v1[26], v2[26];

bool sol() {
    for (int i = 0; i <= 25; i++) v1[i].clear(), v2[i].clear();
    n = read(), m = read();
    scanf("%s", given + 1);
    scanf("%s", target + 1);
    memset(now, 0x7f, sizeof(int) * (m + 2));
    for (int i = 1; i <= n; i++)
        v1[given[i] - 'a'].push_back(i);
    for (int i = 1; i <= m; i++)
        v2[target[i] - 'a'].push_back(i);
    // 循环26个字母：
    for (int i = 0; i <= 25; i++) {
        if (v1[i].size() < v2[i].size()) return false;
        if (v2[i].empty()) continue;
        auto p1 = v1[i].rbegin(), p2 = v2[i].rbegin();

        int mi = 0x7f7f7f7f;
        for (int j = m; j >= 1; j--) {
            if (p1 == v1[i].rend()) return false;
            mi = min(now[j], mi);
            // 试图使即将填入的now[i]小于mi
            if (mi < *p1) {
                while (p1 != v1[i].rend())
                    if (*p1 > mi) p1++;
                    else break;
                if (p1 == v1[i].rend()) return false;
            }
            if (j == *p2) now[*(p2++)] = *(p1++);
            if (p2 == v2[i].rend()) break;  // 当前字母已经填完了
        }
    }
    return true;
}

void tc() {
    int t = read();
    while (t--) {
        if (sol()) printf("YES\n");
        else printf("NO\n");
    }
}

int main() {
    tc();
    return 0;
}

You May Also Enjoy