P6752 Solution

· · 题解

吐槽

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

思路

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

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

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

哪里出了问题呢，按照以上方法，函数 `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$ 了（？）。