1 条题解

  • 0
    @ 2026-11-15 15:51:05

    题目分析

    30 分的做法当然直接 O(n4)O(n^4) 暴力枚举,简直是出题人良心的馈赠。

    将平面绕原点旋转45度,并缩放2倍。然后,原本在 (X,Y)(X,Y) 的点移动到 (X+Y,X−Y)(X+Y,X-Y)。

    令每个点 PiP_i 在此变换后的坐标为 (xi,yi)(x_i, y_i)。则有 xi=Xi+Yix_i = X_i + Y_i 和 yi=Xi−Yiy_i = X_i - Y_i。

    接下来,我们考虑 dist(A,B)\text{dist}(A,B) 的定义是如何变化的。

    在原始定义中,兔子可以从 (X,Y)(X,Y) 跳到 (X+1,Y+1)(X+1,Y+1), (X+1,Y−1)(X+1,Y-1), (X−1,Y+1)(X-1,Y+1), 和 (X−1,Y−1)(X-1,Y-1);

    因此,在变换后,它可以从 (X+Y,X−Y)(X+Y,X-Y) 跳到 (X+Y+2,X−Y)(X+Y+2,X-Y), (X+Y,X−Y+2)(X+Y,X-Y+2), (X+Y,X−Y−2)(X+Y,X-Y-2), 和 (X+Y−2,X−Y)(X+Y-2,X-Y)。

    将 x=X+Yx=X+Y 和 y=X−Yy=X-Y 替换后,它可以从 (x,y)(x,y) 跳到 (x+2,y)(x+2,y), (x,y+2)(x,y+2), (x,y−2)(x,y-2), 和 (x−2,y)(x-2,y)。

    从 AA 到 BB 所需的最小跳跃次数是 dist(A,B)\text{dist}(A,B) 的定义(若无法到达,则 dist(A,B)=0\text{dist}(A,B)=0)。

    接下来,我们考虑变换后的问题。

    即,设 Pi=(xi,yi)P_i=(x_i,y_i),定义 dist(A,B)\text{dist}(A,B),并考虑如下的和:

    $$\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',$$

    其中 (x1′,x2′,…,x∣E∣′)(x_1', x_2', \ldots, x_{|E|}') 是对 (xE1,xE2,…,xE∣E∣)(x_{E_1}, x_{E_2}, \ldots, x_{E_{|E|}}) 进行升序排序后的序列。

    应用相同的讨论到 yy 坐标,可以找到 $\sum_{i=1}^{|E|-1} \sum_{j=i+1}^{|E|} \text{dist}(P_{E_i}, P_{E_j})$;同样的讨论适用于 xix_i 和 yiy_i 都是奇数的组,最终可以找到最终的和。

    对两组的 xx 和 yy 坐标进行排序的时间复杂度为 O(Nlog⁡N)O(N \log N),其余计算的时间复杂度为 O(N)O(N),所以这个问题可以在 O(Nlog⁡N)O(N \log N) 的时间内解。

    • 1

    信息

    ID
    123
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者