题解CF1924E【Paper Cutting Again】

xuanxuan001 · 2024-01-28 11:45:53 · 题解

虽然官方还没出题解，但扫了眼代码感觉我的做法貌似比官方题解简单，所以发篇题解。

又是阴间场，B 的线段树 pushdown 写错了一个变量然后 WA #10 硬瞪了二十分钟还无脑交了两发，但至少没 fst。感觉如果跳过 BD 写个 ACE 都能上大分，但在赛场上又怎么预料得到呢。

发现切割的过程可以转换为从位置 (n,m) 一直走直到位置 (x,y) 满足 xy < k 为止需要移动的期望步数，移动方式是每次等概率走到它正下面（即只有 x 变小）和正右边（即只有 y 变小）的所有点中的一个。

可以将期望步数转换为对于所有 (x,y) 满足 x \le n,y \le m,xy \ge k 的位置，经过 (x,y) 的概率求和。

先不考虑复杂度的问题，考虑对所有的 1 \le X \le n 且 1 \le Y \le m 求出经过 (X,Y) 的概率 P(X,Y)。

需要分为下面几种情况讨论：

2. 1. $x>X$，那么继续减小。 2. $x=X$，那么就经过了目标位置。 3. $x<X$，寄了。 所以综合以上的分讨，发现只需要考虑第一次 $x \le X$ 的时候或者 $y$ 减小时 $x$ 的取值即可，发现此时有 $X+m-1$ 种可能（需要将 $y$ 减小的情况也考虑在内），其中只有一种会经过，所以得到 $P(x,y) = \dfrac 1{X+m-1}$。当然对于数学直觉较好或见过类似问题的选手来说可以不需要很严谨的推导并得出结论。
3. X=n$ 且 $Y<m$，与上面类似，$P(X,Y) = \dfrac 1{Y+n-1}
4. 与 2 和 3 的讨论类似，发现如果一次移动后依然满足 $x>X$ 且 $y>Y$ 就可以不考虑，那么排除掉那些情况后就只有下面这些可能： 1. 减少 $x$ 并且 $x=X$ ，进入下一步分讨。 2. 减少 $x$ 并且 $x<X$ ，寄。 3. 减少 $y$ 并且 $y=Y$ ，进入下一步分讨。 4. 减少 $y$ 并且 $y<Y$ ，寄。 那么上面总共的方案数有 $X+Y$ 种，其中能转换为 2 和 3 的情况的只有 $2$ 种，发现转换后的概率与前面独立，所以最终的概率就是两步的概率的乘积 $P(X,Y) = \dfrac 2{(X+Y)(X+Y-1)}$。

可以手模样例以辅助理解，样例（n = 2,m = 4）的 P 如下：

然后考虑复杂度的问题，由于题目保证了 \sum n,\sum m \le 10^6，所以前面三类情况直接暴力计算都是可以接受的，但第四类有 (n-1)(m-1) 个点，不能直接枚举。

但是发现第四类中 P(X,Y) 只和 X+Y 的值有关，并且这个值只有 O(n+m) 种可能的取值，所以可以考虑枚举这个值并计算有多少个位置要被计入答案。

确定了 N=X+Y 后只需要再确定 X 就能确定唯一的位置，首先要让这个位置 (X,N-X) 在矩形内，这可以确定 X 的一个取值范围 [l,r]。

然后还需要保证 X(N-X) \ge k，可以转换成二次函数 -X^2 + NX - k \ge 0 并解出它的解集，事实证明直接用浮点数不会爆精度。

将这两个区间取交后即可得到有多少个值会被计入，AC记录，感觉没啥好注释的。