自动搬运

查看原文

来自洛谷，原作者为

	vzcx_host vzcx 系列第一站

搬运于2025-08-24 22:23:37，当前版本为作者最后更新于2021-07-11 14:46:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

吐槽

16MB 的空间你交互库确定不会 MLE？

思路

先分析一下伪代码，我们想拿 $100$ 分则 $maxA + maxB$ 必须为 $10$，因此，二进制存储是不行的了（好像一分都拿不到）。

我们不一定只能用二进制，可以考虑更高的进制。比如说三进制，这样我们就把 $3$ 个位置压成一位（反正 $10240$ 长度的数组可以随便用），将其中一个位置变成 $1$，其它位置为 $0$，表示此位的数码。比如三进制数 $(2120)_3$，最后的数组即 001 010 001 100。比大小的时候只需要将 $b$ 也分解，从上往下一位一位比即可。

我们可以先比 $b$ 的最高位在数组中的位置，若 $a$ 的对应位相同，则比次高位，直到找到一个位置不同。若没有不同，则 $a=b$。否则，我们暴力寻找 $a$ 此位对于 $b$ 而言更大还是更小。

$k$ 进制我们的操作次数为 $maxA=\log_k4096,maxB=maxA+\frac{k}{2}$，$k=6$ 左右时 $maxA + maxB$ 最小，约为 $12$。

哪里出了问题呢，按照以上方法，函数 compare 中 $a,b$ 相差越大，则 bit_get 调用次数越少，很不均匀。

为了更均匀地调用 bit_get，我们对每一个数码采取不同的进制。

假设我们只用 $4$ 位，即 $maxA=4$，若最高位不同我们可以找 $6$ 次，所以最高位用 $12$ 进制。相同我们只需要比 $1$ 次，此时考虑第 $2$ 位，不同我们可以找 $5$ 次，所以第 $2$ 位采用 $10$ 进制。不同同样只需比一次。因此，从高位到低位进制分别为 $12$ 进制，$10$ 进制，$8$ 进制，$6$ 进制。

$3$ 位可以表示 $14\times12\times10=1680$ 个数。

$4$ 位可以表示 $12\times10\times8\times6=5760$ 个数。

$5$ 位可以表示 $10\times8\times6\times4\times2=3840$ 个数。

只有 $4$ 位是能表示所有的数。最后再注意一下第二维下标从 $1$ 开始就差不多了。

我的思路和官方题解几乎一样，但 $MLE$ 了（？）。