GZOI2024 Day2 T2【乒乓球】
学习了蔡队的题解。
\(P,Q\le 10^{14}\)。
Alice 一定是赢了 \(Y\) 场比赛，每场比赛 \(X\) 局表示胜利，设 Bob 赢了 \(Z\) 场比赛。
那么每场比赛赢了的人一定赢了 \(X\) 局，输了的人一定赢了 \(<X\) 局。
有：
- \(Z<Y\)
- \(XY\le P\le XY+Z(X-1)\)
- \(ZX\le Q \le ZX+Y(X-1)\)
观察到在 \(ZX\le Q\) 和 \(Z<Y\) 的情况下，把 \(Z\) 取到最大一定是不劣的。感性理解一下，在 \(X,Y\) 固定的情况下，\(Z\) 越大，\(P,Q\) 可操作的空间也越大，更容易符合要求。
因此有 \(Z=\min\{Y-1,\lfloor \frac{Q}{X}\rfloor \}\)。
分类讨论。
- $Z=\lfloor \frac{Q}{X}\rfloor $：
则 \(Z\le Y-1\)。
显然此时第 \(2\) 个不等式恒成立。
由第 \(1\) 个不等式可以得到：\(Y\le \lfloor\frac{P}{X} \rfloor,Y\ge \lceil \frac{P-ZX+Z}{X}\rceil\)，且 \(Y>Z\)。
因此，\(\max\{Z+1,\lceil \frac{P+Z}{X}\rceil-Z\}\le Y \le \lfloor\frac{P}{X} \rfloor\)。
首先按照 \(Z\) 的变化对 \(X\) 进行整除分块。可以证明 \(Z\) 一共有 \(O(\sqrt{Q})\) 种取值。分成 \(O(\sqrt{Q})\) 块。同时按照 \(\lfloor\frac{P}{X} \rfloor\) 进行分块，这样一共有 \(O(\sqrt{n}+\sqrt{P})\) 块。
\(\lceil \frac{P+Z}{X}\rceil=\lfloor \frac{P+Z-1}{X} \rfloor -1\)。
对于这个东西，当 \(X\le \sqrt{P}\) 的时候，因为 \(X\) 一定时 \(Z\) 也确定了，所以 \(\lfloor \frac{P+Z-1}{X} \rfloor\) 取值有 \(O(\sqrt{P})\) 个。
当 \(x> \sqrt{P}\) 的时候，\(Z<X\)，所以 \(\lfloor \frac{P-1}{X} \rfloor\) 一定时，\(\lfloor \frac{P+Z-1}{X} \rfloor\) 也只有两种可能（\(+1\) 或相等）。所以 \(\lfloor \frac{P+Z-1}{X} \rfloor\) 的取值时 \(O(\sqrt{P})\) 的。
所以 \(P,Q\) 同阶，用 \(n\) 表示，一共只有 \(O(\sqrt{n})\) 块。
- \(Z=Y-1\)
\(Z<\lfloor \frac{Q}{X}\rfloor\)。
\(\therefore Y\le \lfloor \frac{Q}{X}\rfloor \\ \therefore Y\le \frac{Q}{X}\\ \therefore XY\le Q\)
把这两个式子搬下来：
\(XY\le P\le XY+Z(X-1)\\ ZX\le Q \le ZX+Y(X-1)\)
显然这两个式子左边恒成立。右边分别是：
- \(P\le 2XY-X-Y+1\)
- \(Q\le 2XY-X-Y\)
发现他们两长得差不多，设 \(R=\max\{P-1,Q\}\)。
则 \(R\le 2XY-X-Y\)。
变成 $X\ge \lceil \frac{R+Y}{2Y-1} \rceil =\lfloor \frac{R+Y-1}{2Y-1} \rfloor +1 $。
同 \(\lfloor \frac{P+Z-1}{X} \rfloor\) 的证明，\(\lfloor \frac{R+Y-1}{2Y-1} \rfloor\) 的取值也只有 \(O(\sqrt{n})\) 种。设 \(V=\lfloor \frac{R+Y-1}{2Y-1} \rfloor\)，对于每一个 \(V\) 我们已经知道了 \(X\) 的取值范围，要求满足的 \(Y\) 的取值范围。
首先因为我们的 \(V\) 一定时按照合法的最小的 \(Y\) 来取的值，所以我们只需要找出 \(Y\) 的上界。即最后一个 \(Y\) 使得 \(\lfloor \frac{R+Y-1}{2Y-1} \rfloor = V\)。
\[\frac{R+Y-1}{2Y-1}\ge V \\ R+Y-1\ge 2YV-V \\ R+V-1\ge (2V-1)Y \\ Y \le \lfloor \frac{R+V-1}{2V-1} \rfloor \]这样就解决了这道题目。总时间复杂度时 \(O(\sqrt{n})\)。
综上所述，感觉该题比较巧妙，而且细节较多，想要场切可能需要一个灵活的大脑（可惜我没有）。整除分块还是个不错的技巧的。
标签：lfloor,le,frac,T2,Day2,rfloor,GZOI2024,ZX,sqrt From： https://www.cnblogs.com/liyixin0514/p/18405286