QOJ1289 A+B Problem 题解

FLY_lai · 2023-08-05 19:50:41 · 个人记录

这题实在太难了，所以单开一个博客写过程

题意：给定一个 01 串 S，选一个子序列填成一个 01 串 A，剩下没选的又构成一个 01 串 B。把这两个 01 串看作二进制数，要求这两个二进制数的和最大。且限制 A,B 长度为 n,m。

（不妨 n<m，即 B 初始更长，n=m 太简单）

贪心：

若 s_1=0，把 0 放进短串。若 s_1=1，如果填进短串里依然能使长串比短串多的部分都是 1，填短串；否则填长串。

引理 1：s_1=0 时存在最优解，s_1 填入了短串。

证明 1：归纳假设 m 更小的情况已经得证了。（当 n=m 时显然成立，因为填哪个都是填入短串）

设 x 为某个方案，将 s_1 填入了长串。我们证明将 x 进行调整后能使 s_1 填入短串，且更优。

1. 情况一：s_2=0，根据归纳，存在一种最优解，s_2 填到了短串上。那既然 s_1=s_2=0，而 s_1 填到长串 s_2 填到短串，也就可以将 s_1 填到短串 s_2 填到长串。此时就是 s_1=0 时填到了短串。

2. 情况二：s_2=1。

   1. 若 s_2 填到了短串。我们可以让 s_1 填到短串，s_2 填到长串，之后的不变。因为长串的数更大，所以得出的结果也更优。

   2. 若 s_2 填到了长串。假设我们在长串又填了一些数，记为 x，第一次往短串填数，填了一个 w。

      1. 那我们进行调整：$s_1$ 往短串填，$s_2,x$ 依旧填长串，$w=0$ 填长串。这样两串的形式就变成：短串是 $\overline{0.....}$，长串是 $\overline{1x0......}$。 $s_1,w$ 都是 $0$，所以短串最高位贡献不变，而 $s_2=1,x$ 都高了一位，答案更优。
      2. 我们也进行和 $w=0$ 一样的调整。两串此时变成 $\overline{0...}$ 和 $\overline{1x1.....}$。 尽管短串的 $1$ 到了长串的 $x$ 后面可能会少一点，但是考虑整体：设原本短串的 $1$ 在第 $j$ 位，长串的 $1$ 在第 $k$ 位，贡献是 $2^j+2^k$；而调整完之后不管短串调到哪里，长串的 $1$ 贡献变为 $2^{k+1}>2^j+2^k$，所以调整完一定更优。

综上，引理 1 得证。草这么难还只是引理 1

引理 2：s_1=1，且如果 s_1 放到短串，无法让长串的最高 m-n 位都是 1 时（也就是比短串最高位更高的位置（不包括短串最高位对应位置）都是 1），存在一种最优解，把 s_1 填入长串。

证明 2：假设 x_0 为一个最优解将 s_1 填入短串。我们尝试调整使得 s_1 填入长串答案不差。

为了方便表述，称长串的比短串最高位更高的位置（不包括短串最高位的对应位置）为 “高部分”。

填了 s_1 后，假设又在短串填了 y_1 个数（可为 0）后在长串填了一个数；又在短串填了 y_2 个数后在长串填了第二个数 ……

根据条件，高部分中一定有 0。我们进行调整：让 s_1 填长串，然后一直到填这个 0 之前都照旧填（此时一些 y 位置更高了），将这个 0 填到短串，之后所有的都不变。

此时在这个 0 之前填的 y 更高了，之后的不变；这个 0 的位置变成 1 了，之后的不变；0 本来就没有贡献，换了位置也没有减少贡献。所以总价值不差。

引理 2 得证。

引理 3：如果 s_1=1，且把它填到短串中可以使高部分全部填 1，则存在一种最优解，把 s_1 填到短串。

证明 3：假设 x 是可以使高部分全 1 且 s_1 填短串的最优解，但把 s_1 填入了长串.

同时设 x_0 为一种填法，是一种把 s_1 填到短串，然后一遇到 0 就填到短串，一遇到 1 就填长串，直到高部分全是 1 为止。

设 x_0 填完 s_1 后，在短串填了 z_1 个 0 后填了长串中第一个 1，z_2,z_3,\dots 类似定义。

设 p 为 S（原 01 数组）的一个前缀，表示当 x_0 将高部分全部填成 1 后，刚好用完 p。

接下来开始分类讨论。

2. 考虑 $p$ 在 $x$ 中是怎么填的。设 $p$ 在长串中填了 $s_1+u$，短串中填了 $s_2+v$，即长串中为 $\overline{1u...}$，短串中为 $\overline{0v....}$。 这个时候我们又按 $u$ 的长度分两种情况。 1. $s_1+u$ 全部都位于高部分，即 $u$ 最右边也严格高于短串的最高位。 调整，我们把 $s_1$ 填到短串。根据条件，我们可以把原本 $s_1+u$ 的位置全部填上 $1$，这显然要比原本的大。 而在短串，最高位上原本是 $0$ 现在是 $1$。已经足够顶掉后面所有数了。 因此最优。 2. $s_1+u$ 最右边有比短串最高位低的。 我们发现按照 $x_0$ 的填法，显然 $p$ 这个前缀的贡献会比 $x$ 中 $p$ 的贡献更大。而对于剩下的 $S-p$，我们发现 $x_0$ 的填法长串剩下的可填位置更多，短串剩下的少；而 $x$ 的填法长串剩下的可填位置和短串更加平均。 而平均就小（感性理解，懒得证了）。所以 $x_0$ 可以优于 $x$。

综上所述，贪心正确。