P9566 [SDCPC2023] K-Difficult Constructive Problem 题解

Coffee_zzz · 2023-08-18 21:35:31 · 题解

首先发现在字符串开头或末尾的 \texttt{?} 不好考虑，那我们就特殊判断，把 \texttt{?} 拆成 \texttt{0} 和 \texttt{1}。

接下来，我们求出把 s 中的每一个 \texttt{?} 都修改后，满足条件的下标的数量的下限 a 和上限 b。当不满足 a \le k \le b 时显然无解。

同时，由于把一个原本是 \texttt{?} 的位置从 \texttt{1} 修改为 \texttt{0} 或从 \texttt{0} 修改为 \texttt{1}，满足条件的下标的数量会加减 2 或不变。所以，当 a 和 k 的奇偶性不同时也无解。当然，显然地，a 和 b 的奇偶性一定是相同的，所以我们不需要考虑 b 和 k 的奇偶性。

这样就判断完无解的条件了，接下来我们考虑构造。

我们首先把所有的 \texttt{?} 都修改为 \texttt{0}，此时字典序最小，求出满足条件的下标的数量 cnt。

当 cnt=k 时，答案合法且最优，直接输出即可。

当 cnt \gt k 时，我们要减少相邻两个元素不同的数量，把一些 \texttt{?} 从 \texttt{0} 修改为 \texttt{1}。

当 cnt \lt k 时，我们要减少增加两个元素不同的数量，还是要把一些 \texttt{?} 从 \texttt{0} 修改为 \texttt{1}。

为了使答案的字典序尽可能小，我们贪心地从右往左修改。注意，有些时候一些修改是没有用的，我们不能进行这些修改。

最后，直接输出修改完的字符串 s 即可。