KingdomAndDice

作者：陈俊锟 汪乐平 钟知闲 徐明宽

关键词：DP 背包 多重背包

题目简述

给出两个长度均为 $n$ 的数组 $\{a_i\}$ 和 $\{b_i\}$，其中 $a_i$ 中有一些位置是 $0$。你需要将 $\{a_i\}$ 中若干个 $0$ 修改成其他的数，要求最终的数组 $\{a_i\}$ 满足：

1. $\{a_i\}$ 中，所有数都是 $[0, x]$ 之间的整数

2. 所有正整数在$\{a_i\}$和$\{b_i\}$中的出现次数加起来不超过$1$

在此基础上，设 $p$ 为“随机两个 $[1,n]$ 之间的整数 $i,j$”后，“$a_i > b_j$”这一事件发生的概率，要求选择一种修改 $\{a_i\}$ 的方式，使得 $|p-0.5|$ 最小。

要求返回使得 $|p-0.5|$ 最小的 $p$。如果存在多个 $p$，输出较小的那个。$n\le 50, x \le 10^9$。

算法一

首先，这两个数组的下标是没有意义的，因此我们可以把它们看成可重集合。

其次，我们可以将取到某个 $a_i$ 的概率分别考虑。如果这个 $a_i\ne 0$，那么它对 $p$ 的贡献也确定了。如果不将它修改为非 $0$ 的值，那么它对 $p$ 没有贡献。否则，如果将 $b_i$ 数组中的数排序，那么可以将 $[1, x]$ 中分成若干段，其中每一段内取不管取哪一个数对 $p$ 的贡献都是相同的。

设布尔数组 $f(i,j)$ 表示已经改掉了 $i$ 个 $0$ 时，是否存在一种方案使得 $p = \frac{j}{n^2}$。我们把对 $p$ 的贡献相同的数在一起考虑。那么问题就转化为了一个经典的多重背包问题，直接 DP 求解即可。

最后，我们就可以得出所有可行的 $p$，直接计算答案即可。

时间复杂度：$O(n^4 \log n)$。

关于时间复杂度

通常采用二进制分组的方法实现多重背包，即对于 $\{b_i\}$ 数组中 $b_i$ 到 $b_{i+1}$ 连续的一段，如果 $\{a_i\}$ 数组中满足 $b_i < a_j < b_{i+1}$ 的 $j$ 个数为 $x$，那么相当于 $v=b_{i+1}-b_i-1-x$ 个大小为 $i$ 的物品，将其拆成 $t$ 个大小依次为 $2^0,2^1,2^2,...,2^{t-2},v-2^{t-1}+1$ 的物品（其中整数 $t$ 满足 $v < 2^t \le 2v$），然后做0-1背包。这样的物品总数为 $O(n\log n)$。用上述做法的时间复杂度和空间复杂度分别为 $O(n^4 \log n)$ 和 $O(n^3)$（如果使用滚动数组）。

虽然这个做法实际上已经可以通过了（毕竟 $n=50$ 时 $\log_2 n$ 很小），但我们有时间复杂度更优的算法。以下给出两种算法：

1、修改状态表示。设 $f(k,i,j)$ 为从前 $k$ 个段（段的意义如上文所述，同一段内取每个数对 $p$ 贡献相同）中选取 $i$ 个数改成 $0$ 并使得 $p = \frac{j}{n^2}$，第 $k$ 个段至少要选多少个数改成 $0$。转移时只需枚举是否从第 $k$ 个段中取数，同时注意第 $k$ 段已取满的状态不能再转移即可。这样的时间复杂度和空间复杂度分别为 $O(n^4)$ 和 $O(n^3)$（如果使用滚动数组将 $k$ 这一维滚掉）。

2、使用压位技巧。仍然用二进制分组的做法，注意到 $f(i,j)$ 是由 $f(i-v,j-c)$ 转移过来的（$v$ 为个数，$c$ 为贡献），因此相当于将 $f(i,j)$ 这个布尔数组进行移位然后做按位或运算，使用压位技巧即可做到 $O(\frac{n^4 \log n}{w})$，其中 $w$ 为字长（通常 $w=32$ 或 $w=64$）。

算法二

其实并没有必要把改掉多少个$0$放到状态定义里面……设 $f(k,j)$ 表示从前 $k$ 个段中选取至少几个数改成 $0$ 才能使得 $p = \frac{j}{n^2}$，转移时枚举从第$k$段取数的个数即可。最后一个$p$可行当且仅当$f(n,p)$不超过初始$a$数组中$0$的个数。这样暴力地实现就是$O(n^4)$的时间、$O(n^3)$的空间，加上滚动数组就是$O(n^2)$的空间，加上二进制分组变成01背包就是$O(n^3 \log{n})$的时间了。（这里滚动数组并不需要开第一维大小为$2$的二维数组，直接在一个大小为$n^2$的数组上DP即可，可以节省一定的代码量）