题解：CF2174A Needle in a Haystack

swate114514 · 2025-12-11 14:24:37 · 题解

打的第一场 CF 竟然有题能写题解诶。

题目要求要使调换 t 的位置后，s 成为 t 的子序列。因为可以随便调换 t 的位置，所以只有 s 中的字符没有在 t 出现过才会输出 Impossible。因为只有小写字母，开桶记录即可。

然后如果可以满足题意，我们可以分两部分处理：

比如 s 串为 aba，t 串为 ababa，我们可以分成 aba 和 ba 两部分处理。

这样的好处是把题目里的约束剥离出来。对于第二部分是显然的，直接按字典序排序即可。因为使 s 成为重排后 t 的子序列只跟第一部分的顺序有关。

然后考虑在不改变第一部分顺序的情况下使字典序最小。

前面的字典序肯定越优越好，那我们不妨双指针，i 指向 t_i，j 指向 s_j。

• 当 t_i \le s_j 时插入这个字符是最优的，可以插入这个字符，i,j 指针右移；
• 当 t_i > s_j 时插入这个字符不是最优的，i 指针右移。

::::success[AC code] ::::