1 条题解
-
0
题目分析
30 分的做法当然直接 暴力枚举,简直是出题人良心的馈赠。
将平面绕原点旋转45度,并缩放2倍。然后,原本在 的点移动到 。
令每个点 在此变换后的坐标为 。则有 和 。
接下来,我们考虑 的定义是如何变化的。
在原始定义中,兔子可以从 跳到 , , , 和 ;
因此,在变换后,它可以从 跳到 , , , 和 。
将 和 替换后,它可以从 跳到 , , , 和 。
从 到 所需的最小跳跃次数是 的定义(若无法到达,则 )。
接下来,我们考虑变换后的问题。
即,设 ,定义 ,并考虑如下的和:
$$\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \text{dist}(P_i, P_j) $$,使用上述定义的 $\text{dist}(A,B)$。 显然,这会得到与原始问题相同的答案。 我们进一步考虑 $A=(x_1,y_1)$ 和 $B=(x_2,y_2)$ 之间的 $\text{dist}(A,B)$。 如果 $x_1 \not\equiv x_2 \pmod{2}$ 或 $y_1 \not\equiv y_2 \pmod{2}$,兔子无法从 $A$ 到达 $B$,所以 $\text{dist}(A,B)=0$。 否则,它正好等于曼哈顿距离的一半,即 $\frac{1}{2}(|x_1 - x_2| + |y_1 - y_2|)$。 注意到 $x_i = y_i + 2Y_i \equiv y_i \pmod{2}$ 对所有 $i$ 成立,这些 $N$ 个点可以分为两组:$x_i$ 和 $y_i$ 都是偶数,或者 $x_i$ 和 $y_i$ 都是奇数。 对于属于不同组的两个点 $A$ 和 $B$,$\text{dist}(A,B)=0$;对于属于同一组的两个不同点,$\text{dist}(A,B)= \frac{1}{2}(|x_1 - x_2| + |y_1 - y_2|)$。 设 $E=\{E_1, E_2, \ldots, E_{|E|}\}$ 是一组点,其中 $x_i$ 和 $y_i$ 都是偶数,那么 $$ \sum_{i=1}^{|E|-1} \sum_{j=i+1}^{|E|} \text{dist}(P_{E_i}, P_{E_j}) = \frac{1}{2} \sum_{i=1}^{|E|-1} \sum_{j=i+1}^{|E|} |x_{E_j} - x_{E_i}| + \frac{1}{2} \sum_{i=1}^{|E|-1} \sum_{j=i+1}^{|E|} |y_{E_j} - y_{E_i}|.$$我们可以找到如下和:
$$\sum_{i=1}^{|E|-1} \sum_{j=i+1}^{|E|} |x_{E_j} - x_{E_i}| = \sum_{i=1}^{|E|-1} \sum_{j=i+1}^{|E|} (x_j' - x_i') = \sum_{i=1}^{|E|} (|E|+1-2i)x_i',$$其中 是对 进行升序排序后的序列。
应用相同的讨论到 坐标,可以找到 $\sum_{i=1}^{|E|-1} \sum_{j=i+1}^{|E|} \text{dist}(P_{E_i}, P_{E_j})$;同样的讨论适用于 和 都是奇数的组,最终可以找到最终的和。
对两组的 和 坐标进行排序的时间复杂度为 ,其余计算的时间复杂度为 ,所以这个问题可以在 的时间内解。
- 1
信息
- ID
- 123
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者