题解：AB-Strings

题目描述

给定两个仅由字符 $'a'$ 和 $'b'$ 组成的字符串 $s$ 和 $t$。每次操作可以选择 $s$ 的一个前缀和 $t$ 的一个前缀（可以为空或整个字符串）进行交换。目标是通过一系列操作，使得最终一个字符串全由 $'a'$ 组成，另一个全由 $'b'$ 组成。要求操作次数尽可能少。

题目理解

关键约束：

• 字符串只包含字符 $'a'$ 和 $'b'$
• 交换操作针对两个字符串的前缀
• 目标状态：一个字符串全 $'a'$，另一个全 $'b'$
• 需要最小化操作次数

问题转化

将问题从字符串操作转化为字符块管理问题：

• 每个字符串可以表示为连续的相同字符块序列
• 交换前缀操作相当于重新分配字符块
• 目标是将所有 $'a'$ 块集中到一个字符串，所有 $'b'$ 块集中到另一个字符串

核心思路

双栈模拟算法

使用两个栈分别维护两个字符串的字符块，通过贪心策略逐步分离 $'a'$ 和 $'b'$：

字符块表示

vector<pair<bool, int>> a[2];  // bool: 字符类型(a=true, b=false), int: 连续长度

关键操作策略

情况1：栈顶字符相同 $(solve1)$

• 当两个栈顶都是 $'a'$ 或都是 $'b'$ 时
• 根据栈的大小关系选择不同的交换策略：
  • 对方栈有多个块：交换当前栈的两个块到对方栈
  • 当前栈较大：交换三个块到对方栈
  • 当前栈中等：交换两个块
  • 当前栈较小：交换一个块

情况2：栈顶字符不同 $(solve2)$

• 当栈顶一个是 $'a'$，一个是 $'b'$ 时
• 根据栈的大小优势选择策略：
  • 当前栈有优势且较大：交换三个块
  • 否则：简单交换栈顶块

算法实现

数据结构

vector<pair<bool, int>> a[2];  // 字符块栈
vector<pair<int, int>> res;    // 操作序列：(s前缀长度, t前缀长度)

预处理

// 将字符串转换为字符块序列，合并相邻相同块
for (int i = n; i; i--) {
    push(0, make_pair(s[i] == 'a', 1));
}
for (int i = m; i; i--) {
    push(1, make_pair(t[i] == 'a', 1));
}

主循环

while (a[0].size() > 1 || a[1].size() > 1) {
    if (a[0].back().first == a[1].back().first) {
        solve1(a[0].size() < a[1].size());
    } else {
        solve2(a[0].size() < a[1].size());
    }
}

关键函数

字符块压入（自动合并相邻相同块）：

void push(bool x, pair<bool, int> v) {
    if (a[x].empty() || a[x].back().first != v.first) {
        a[x].push_back(v);
    } else {
        a[x].back().second += v.second;
    }
}

情况1处理 $(solve1)$：

void solve1(bool fr) {
    if (a[!fr].size() > 1) {
        // 交换两个块到对方栈
        auto tmp1 = get_top(fr), tmp2 = get_top(fr), tmp3 = get_top(!fr);
        push(!fr, tmp2); push(!fr, tmp1); push(fr, tmp3);
        add_res(tmp1.second + tmp2.second, tmp3.second, fr);
    } else {
        // 根据当前栈大小选择策略
        if (a[fr].size() > 4) {
            // 交换三个块
            auto tmp1 = get_top(fr), tmp2 = get_top(fr), tmp3 = get_top(fr);
            push(!fr, tmp3); push(!fr, tmp2); push(!fr, tmp1);
            add_res(tmp1.second + tmp2.second + tmp3.second, 0, fr);
        } else if (a[fr].size() == 3) {
            // 交换两个块
            auto tmp1 = get_top(fr), tmp2 = get_top(fr), tmp3 = get_top(!fr);
            push(!fr, tmp2); push(!fr, tmp1); push(fr, tmp3);
            add_res(tmp1.second + tmp2.second, tmp3.second, fr);
        } else {
            // 交换一个块
            auto tmp1 = get_top(fr);
            push(!fr, tmp1);
            add_res(tmp1.second, 0, fr);
        }
    }
}

复杂度分析

• 时间复杂度：$O(n + m)$，其中 $n$ 和 $m$ 是字符串长度
• 空间复杂度：$O(n + m)$，用于存储字符块和操作序列
• 操作次数：最优或接近最优，满足题目评分标准

示例分析

样例1

输入：

bab
bb

处理过程：

1. 初始状态：

   • $s = [(b,1), (a,1), (b,1)]$
   • $t = [(b,2)]$

2. 第一次交换：$s$ 前缀长度 $1$ 与 $t$ 前缀长度 $0$ 交换

   • $s = [(a,1), (b,1)]$ → ab
   • $t = [(b,1), (b,2)]$ → bbb

3. 第二次交换：$s$ 前缀长度 $1$ 与 $t$ 前缀长度 $3$ 交换

   • $s = [(b,4)]$ → bbbb
   • $t = [(a,1)]$ → a

输出：

2
1 0
1 3

样例2

输入：

bbbb
aaa

输出：

0

（已满足目标状态）

算法标签

• 字符串处理
• 数据结构 - 栈、双栈模拟
• 算法策略 - 贪心算法、模拟法
• 优化技巧 - 合并相邻相同块、状态压缩

总结

本题通过将字符串表示为字符块序列，利用双栈模拟和贪心策略，实现了高效的前缀交换操作：

1. 问题转化：将字符串操作问题转化为字符块管理问题
2. 核心算法：使用双栈维护字符块，根据栈顶状态选择最优交换策略
3. 性能保证：线性时间复杂度，操作次数最优或接近最优
4. 实现简洁：通过精心设计的交换策略，代码清晰且高效

该解法能够处理大规模输入（$|s|, |t| \leq 2 \times 10^5$），并满足题目要求的各种评分标准。