题目大意

给定一个基因串的压缩表示，允许进行一次操作（插入/删除/替换字符），要求找出两种操作方案：

1. 使操作后的压缩串长度 最小
2. 使操作后的压缩串长度 最大

压缩规则

• 连续相同字符压缩为 数字+字母
• 如果连续个数为1，只保留字母
• 例：AAAAACAAAAACC → 5AC5A2C

核心思路

1. 压缩长度计算

压缩长度取决于连续段的划分和数字的位数：

• 一个长度为 k 的连续段贡献：位数(k) + 1（数字位数 + 1个字母）
• 特别地，当 k = 1 时只贡献 1（没有数字）

位数(k) 函数：

int cnt(int x) {
    if (x == 1) return 0;  // 长度为1时不写数字
    int ans = 0;
    while (x) {
        x /= 10;
        ans++;
    }
    return ans;  // 返回数字的位数
}

2. 操作的影响分析

删除操作：

• 在连续段中间删除：可能分裂成两个段
• 在长度为1的段删除：可能连接前后相同字符的段
• 目标：最小化时促进合并，最大化时促进分裂

插入操作：

• 在相同字符间插入相同字符：增加连续长度
• 在不同字符间插入新字符：增加新段
• 目标：最小化时减少段数，最大化时增加段数

替换操作：

• 将字符改为相邻字符：可能连接两个段
• 将字符改为不同字符：可能分裂段
• 目标：最小化时创造长连续段，最大化时创造多短段

3. 算法策略

• 解析压缩串，重建连续段信息 vector<pair<长度, 字符>>
• 枚举所有可能的操作位置和类型，计算对压缩长度的影响
• 分别记录最小化和最大化的最优方案

主要流程

1. 解析输入：将压缩串转换为连续段列表
2. 初始化：设置极大极小值
3. 枚举删除操作：考虑各种边界情况
4. 枚举插入操作：考虑段中间、段边界插入
5. 输出结果：按格式输出两种操作方案

复杂度分析

• 时间复杂度：$O(|T|)$，其中 $|T|$ 是压缩串长度
• 空间复杂度：$O(|T|)$，存储连续段信息

总结

本题的关键在于深入理解RLE压缩机制，分析各种操作对连续段结构的影响。通过分类讨论所有可能的情况，找到最优的操作方案。题目考验对字符串处理的熟练度和细致的问题分析能力。