题解 | #字符串min-22#

题目描述

Tk 有一个长度为 的小写字母字符串 ，和一个长度为 的小写字母字符串 。他可以执行如下操作任意次：

• 若 ，选择两个不同奇偶性下标（1-based）的字符删除，并将剩余字符按原顺序拼接（下标重新从 1 开始分配）。

目标是使 的字典序严格小于 ，求最少操作次数；若无法达成，输出 。

本题是二分答案 + 贪心构造 + 奇偶约束处理类型的题目，难度困难。

核心思路

核心观察

• 每次操作删除 1 个奇数位 + 1 个偶数位（1-based），因此：
  • 最多可操作 次；
  • 操作 次后，保留 个原始奇数位、 个原始偶数位。
• 目标函数具有单调性：若 次操作可行，则 也可行（删更多字符只会让字典序更小或不变）。
• 因此可对操作次数 进行二分搜索，关键在于实现高效的 check(c) 函数。

算法步骤

1. 二分答案：在 范围内二分最小操作次数 。
2. check(c) 函数：
   • 若 ，直接比较 与 。
   • 否则，模拟删除过程，构造字典序最小的s的合法子序列：
     • 使用栈贪心保留尽可能小的前缀；
     • 通过 c = 2c - 1 和 c++ trick 隐式维护“删奇=删偶”约束；
     • 若只删了一种奇偶性，通过 nflag 数组调整，强制保留另一种奇偶字符；
   • 比较构造结果与 的字典序。
3. 输出二分结果。

正确性分析

• 单调性成立：在贪心构造最小字典序的前提下，保留字符越少，结果字典序不会变大。
• 奇偶合法性保障：
  • 贪心阶段通过 c++ 补偿奇偶配对；
  • 最终通过 nflag 调整确保删奇 = 删偶；
• 字典序最优性：贪心栈 + 安全删除位置（nflag=1）保证构造结果为当前约束下的最小字典序。

复杂度分析

• 时间复杂度：
  • 单次 check 为 ，二分 ，总时间 ；
  • 题目保证 ，实际运行高效。
• 空间复杂度：
  • ，用于存储栈、奇偶标记和 nflag 数组。

代码

#include <bits/stdc++.h>
using namespace std;

string s, t;
char ch[200000];          // 模拟栈，存储当前保留的字符
int col[200000];          // col[i] 表示 ch[i] 在原字符串 s 中的位置奇偶性（0: 奇数位(1-based)，1: 偶数位）
int nflag[200000];        // nflag[i]: 从位置 i 开始的后缀是否“非递减”（用于后续调整）

// 检查是否能在 c 次操作内使得 s 变成字典序 < t 的字符串
// 注意：c 是操作次数（每次删 2 个字符），但函数内部做了特殊转换
bool check(int n, int m, int c) {
    int i, p = 0, f, flag = -2, d;

    // 特判：0 次操作
    if (c == 0) {
        for (i = 0; i < n && i < m; i++) {
            if (s[i] < t[i]) return 1;   // s < t
            if (t[i] < s[i]) return 0;   // s > t
        }
        if (i == m) return 0;            // t 是 s 的前缀，且 s 更长 → s >= t
        return 1;                        // s 是 t 的真前缀 → s < t
    }

    // 关键 trick：将操作次数 c 转换为“最多可删除的字符数 - 1”
    // 因为每次操作删 2 字符，总共可删 2*c 个，这里设 c = 2*c - 1
    c = c * 2 - 1;

    // 贪心构造字典序最小的字符串（用栈）
    for (i = 0; i < n; i++) {
        // 尝试弹出栈顶更大的字符，前提是还有删除额度（c > 0）
        while (p > 0 && ch[p - 1] > s[i] && c > 0) {
            if (flag == -2) flag = col[p - 1];// 记录第一个被删字符的奇偶性
            if (flag != col[p - 1] &&
                    flag != -1) {// 如果删了不同奇偶性的字符
                flag = -1;// 标记为“已删两种”
                c++;// 补偿一次删除额度（因为合法操作必须奇+偶配对）
            }
            c--;// 消耗一次删除额度
            p--;// 弹出栈顶
        }
        // 将当前字符压入栈
        col[p] = i % 2;   // 记录该字符在原串中的位置奇偶性（0-based 下标）
        ch[p] = s[i];
        p++;
    }

    // 如果还有删除额度，从末尾继续删（贪心）
    while (p > 0 && c > 0) {
        if (flag == -2) flag = col[p - 1];
        if (flag != col[p - 1] && flag != -1) {
            flag = -1;
            c++;
        }
        c--;
        p--;
    }

    // 构建 nflag 数组：nflag[i] = 1 表示从 i 到末尾是非递减的
    nflag[p - 1] = 1;
    for (i = p - 2; i > -1; i--) {
        if (ch[i] == ch[i + 1])
            nflag[i] = nflag[i + 1];// 相等，继承后缀性质
        else if (ch[i] > ch[i + 1])
            nflag[i] = 1;// 当前 > 后面，说明从 i 开始不是递增，但可能用于调整
        else
            nflag[i] = 0;// 当前 < 后面，是递增的
    }

    // 如果只删除了一种奇偶性的字符（flag != -1），需要强制保留至少一个另一种奇偶性的字符
    // （因为每次操作必须删一个奇 + 一个偶，不能只删一种）
    if (flag != -1) {
        d = -1;
        // 优先找一个“非 flag 类型”且“从它开始后缀非递减”的位置
        for (i = 0; i < p; i++) {
            if (col[i] != flag && nflag[i]) {
                d = i;
                break;
            }
        }
        if (d == -1) {
            // 没找到，就找最后一个“非 flag 类型”的字符
            for (i = p - 1; i > -1; i--) {
                if (col[i] != flag) {
                    d = i;
                    break;
                }
            }
        }
        // 删除这个字符（相当于微调保留的字符串，以满足奇偶配对约束）
        for (i = d + 1; i < p; i++) {
            ch[i - 1] = ch[i];
        }
        p--;
    }

    // 最终比较构造出的字符串 ch[0:p] 和 t
    for (i = 0; i < p && i < m; i++) {
        if (ch[i] < t[i]) return 1;
        if (t[i] < ch[i]) return 0;
    }
    if (i == m) return 0;   // t 是前缀，且 ch 更长 → ch >= t
    return 1;               // ch 是 t 的真前缀 → ch < t
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T, n, m, l, r, mid;
    cin >> T;
    while (T--) {
        cin >> n >> m >> s >> t;

        // 二分答案：操作次数 c 的范围是 [0, (n+1)/2)
        int low = 0, high = (n + 1) /2-1;// 搜索范围 [0, max_c - 1]
        int ans = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (check(n,m,mid)) {
                ans = mid;        // 记录可行解
                high = mid - 1;   // 继续找更小的
            } else {
                low = mid + 1;
            }
        }

// ans 就是最小可行 c；若从未更新，则为 -1
        if (ans == -1) cout << "-1\n";
        else cout << ans << '\n';
    }
    return 0;
}