World Tour Finals 2019 D – Distinct Boxes 题解

太神了,专门写一篇题解 qwq

简要题意:给你 \(R\) 个红球和 \(B\) 个蓝球,你要把它们放到 \(K\) 个箱子里,要求没有两个箱子完全相同(即两种球个数就相同),求 \(K\) 的最大值。

设第 \(i\) 个箱子中有 \(x_i\) 个红球,\(y_i\) 个蓝球,就变成了找平面上一个大小最大的点集 \((x_i,y_i)\),使 \(\sum x_i =R, \sum y_i=B\)。进一步,由于可以直接将 \(x\) 最大的点 \(x\) 坐标变大,\(y\) 同理,因此只需有 \(\sum x_i \le R, \sum y_i \le B\) 即可。

这是一道二维平面上的题,我们可以想办法把它变成一维。给 \(x\) 方向赋一个权重 \(p\)\(y\) 方向赋一个权重 \(q\),那么一个点 \((x,y)\) 就被投影到了 \(px+qy\) 上。此时我们发现所有点投影后的权重和为 \(\sum px_i+qy_i=p\sum x_i+q\sum y_i\),于是当 \(\sum x_i \le R, \sum y_i \le B\) 时,便有 \(\sum px_i+qy_i\le pR+qB\)。在某种程度上,我们就会希望 \(\sum px_i+qy_i\) 尽量小。

首先当然二分 \(K\),问题变为判定一个 \(K\) 是否可行。然后我们考虑一个凸包,凸包上的点 \((X,Y)\) 代表 \(\sum x_i=X\) 时,\(\sum y_i\) 的最小值为 \(Y\)。感性理解一下这玩意大概就是凸的,并且对每个 \(X\) 都有定义。于是 \(K\) 可行当且仅当点 \((R,B)\) 在凸包上方。又发现对于一个 \((p,q)\),使 \(p\sum x_i+q\sum y_i\) 最小时,\((\sum x_i,\sum y_i)\) 一定在凸包上,于是我们尝试用 \((p,q)\) 搞出凸包上的一些点。

继续发现 \(p\sum x_i+q\sum y_i=(p,q)\cdot (\sum x_i,\sum y_i)\),即向量 \((x_i,y_i)\) 在向量 \((p,q)\) 上的投影。\(p\sum x_i+q\sum y_i\) 最小,就是这个投影最小,可以看作拿一条与向量 \((p,q)\) 垂直的直线去切这个凸包,所以每个点都一定有机会被切到,且 \((p,q)\) 的斜率越大,切到的点越偏右。于是再对 \((p,q)\) 的斜率进行二分,如果发现求出来的点 \((\sum x_i,\sum y_i)\)\((R,B)\) 左下方,那就成了;如果在 \((R,B)\) 右上方,那就寄了;如果在左上方,那就增大斜率;如果在右下方,那就减小斜率。

这里有两个技巧:1,不要在实数域上二分 \((p,q)\) 的斜率,令 \(p+q=10^9+7\)(或其它常数),然后直接二分 \(p\),可以发现这样基本上能覆盖到所有的斜率都能被弄到,从而能切到每个点。2,由于凸包上相邻两条线段斜率可能非常相近,因此我们要当发现当前凸包上一条连线在 \((R,B)\) 下方时直接返回合法。

最后的问题是如何计算对于一个 \((p,q)\) 计算 \(p\sum x_i+q\sum y_i\) 的最小值。我们二分一个 \(z\),求出 \(p\sum x_i+q\sum y_i\le z\) 的个数进行二分。然后求出 \(p\sum x_i+q\sum y_i\le z\)\(x,y\) 分别的和以及多余的一些 \(p\sum x_i+q\sum y_i=z+1\) 的前若干个 \(x,y\) 的和。以上操作全部用类欧做就是一个 \(\log\),或者发现如果我们选了一个点 \((x,y)\),那么它左下角的所有点都一定已经被选了,所以有 \(\min(x,y)\le O(W^{1\over 3})\)\(W\) 为值域),二维分别枚举即可。

一共三个二分,最后一步用类欧时间复杂度就 \(O(\log^4 W)\),直接枚举复杂度就 \(O(W^{1\over 3}\log^3 W)\)

张贴在2