博德之跃 3(SCCPC 2026)

不知道是老了还是怎么样，感觉现在做贪心的题目很吃力啊！

贪心地考虑问题。对于 A\text{A} 序列串 s[l…r]\text{s}[l\dots r]，如果 sl≠srs_l\neq s_r，那么选字典序较小的弹出。

剩下的情况就是 sl=srs_l=s_r，令 c=sl=src=s_l=s_r，ii 为从左到右第一个不等于 cc 的下标，jj 为从右到左第一个不等于 srs_r 的下标。分类讨论问题：

  • 当 si,sj>cs_i,s_j\gt c 时，尽可能拖延 cc 的时长，所以 A\text{A} 序列左右弹出所有 cc 以及 B\text{B} 序列后面补上长度为 max⁡(i−l,r−j)\max(i-l,r-j) 的 cc 串。
  • 当 si,sjs_i,s_j 有一个 <c\lt c，一个 >c\gt c 时，不失一般性地假设 si<c<sjs_i\lt c\lt s_j。则我们尽可能让 sis_i 尽快出现，所以左边弹出 i−li-l 个 cc，右边弹出 min⁡(i−l,r−j)\min(i-l,r-j) 个 cc，以及 B\text{B} 序列后面补上长度为 i−li-l 的 cc 串。
  • 当 si,sj<cs_i,s_j\lt c 且 si=sjs_i=s_j 时，可是尽可能让 si/sjs_i/s_j 尽快出现，所以左右边各弹出 min⁡(i−l,r−j)\min(i-l,r-j) 个 cc，以及 B\text{B} 序列后面补上长度为 min⁡(i−l,r−j)\min(i-l,r-j) 的 cc 串。
  • 当 si,sj<cs_i,s_j\lt c 且 si≠sjs_i\neq s_j 时，不失一般性地假设 si<sjs_i\lt s_j。同样地，我们尽可能让 sis_i 尽快出现，所以左边弹出 i−li-l 个 cc，出于字典序最小的考虑，sjs_j 越早出现一定是更优的，所以右边弹出 min⁡(i−l,r−j)\min(i-l,r-j) 个 cc，以及 B\text{B} 序列后面补上长度为 i−li-l 的 cc 串。

感觉讲得不是很好，如果有问题可以评论或者私信问问。