自动搬运

查看原文

来自洛谷，原作者为

	Coffee_zzz 沉覆z

搬运于2025-08-24 22:49:38，当前版本为作者最后更新于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$ 即可。