P9827 [ICPC2020 Shanghai R] Sky Garden题解

Y204335

2024-11-20 10:15:23

Solution

[ICPC2020 Shanghai R] Sky Garden

给个 O(1) 的做法。

题目大意

有 n 个半径从 1 到 n 的同心圆和 m 条过圆心且平分这些圆（把每个圆都分为相等的 2m 段弧）的直线，构成 n+m 条道路，问所有道路的交叉点两两间最短距离的和。

题目分析

由于有 \pi，可能有精度问题，所以先将答案写成 ans_1\pi+ans_2 的形式，最后再计算结果。

先考虑 A\to B 什么时候距离最短（设 A 所在圆的半径为 a，B 所在圆的半径为 b，相隔 k 段弧，钦定 a\ge b），有两种候选路径：先走到 B 所在的圆，再走一段弧到 B；直接走到圆心，再走到 B。考虑两种路径的距离：

s_1=\left(a-b\right)+\frac{kb\pi}{m} s_2=a+b

显然，当 k<\frac{2m}{\pi} 时 s_1<s_2，当 k>\frac{2m}{\pi} 时 s_1>s_2，分别考虑两种走法的贡献（设 x=\left\lfloor\frac{2m}{\pi}\right\rfloor）：

  1. 对于每一个距离圆心 c 的点 C（c>0），C 会被所有与 C 在同一射线且 a\ge c 的 A 经过，并且从 C 可以到达 2x+1 个点，对 ans_1 的贡献为 \left(n-c+1\right)\times2\times\sum_{i=1}^{x}\frac{ic}{m}，对 ans_2 的贡献为 \left(2x+1\right)\times\sum_{i=1}^{n-c}i。在同一个圆上共有 2m 个 C，单个圆上的对 ans_1 的贡献为 c\left[2\left(n-c\right)+1\right]x\left(x+1\right)（A 和 C 在同一圆上会把贡献算两遍，要减去），对 ans_2 的贡献为 2m\left(2x+1\right)\frac{\left(n-c+1\right)\left(n-c\right)}{2}。

  2. 对于每对 A_1,A_2（一个圆与一条直线的两个交点），在每个 b（b\le a）可以走到 \left(m-x-1\right)\times 4+2 个 B（等下去重），对 ans_2 的总贡献为 \sum_{i=1}^{a}\left[\left(m-x-1\right)\times4+2\right]\left(a+i\right)，同一圆上共有 m 对，总贡献为 m\times\left\{\sum_{i=1}^{a-1}\left[\left(m-x-1\right)\times4+2\right]\left(a+i\right)\right\}+\frac{\left[\left(m-x-2\right)\times4+1\right]\times2am}{2}，化简得到对 ans_2 的贡献为 m\left[\left(m-x-1\right)\times4+2\right]\left[a^2+\frac{i\left(i-1\right)}{2}\right]。

此外当 m>1 时圆心会有交点，对 ans_2 的贡献为 \sum_{i=1}^{n}2mi。

分别化简 m=1 与 m>1 的贡献式：

\begin{aligned}ans_2&=\sum_{c=1}^{n}\left(2\times\sum_{i=1}^{c-1}c+i\right)+2c\\&=\sum_{c=1}^{n}2c\left(c-1\right)+\left(c-1\right)c+2c\\&=\sum_{c=1}^{n}4c^2-2c\\&=4\times\frac{2n^3+3n^2+n}{6}+2\times\frac{n\left(n+1\right)}{2}\\&=\frac{4n^3+3n^2-n}{3}\end{aligned}
\begin{aligned}ans_1&=\sum_{c=1}^{n}c\left[2\left(n-c\right)+1\right]x\left(x+1\right)\\&=\sum_{c=1}^{n} x\left(x+1\right)\left[c^2+\left(2n-1\right)c\right]\\&= x\left(x+1\right)\left\{\left(\sum_{c=1}^{n}c^2\right)+\left[\left(2n-1\right)\sum_{c=1}^{n}c\right]\right\}\\&= x\left(x+1\right)\left[\frac{2n^3+3n^2+n}{6}+\left(2n-1\right)\frac{n\left(n+1\right)}{2}\right]\\&=\frac{\left(2n^3+3n^2+n\right)x^2+\left(2n^3+3n^2+n\right)x}{6}\end{aligned} \begin{aligned}ans_2&=\left\{\sum_{c=1}^{n}2m\left(2x+1\right)\frac{\left(n-c+1\right)\left(n-c\right)}{2}+m\left[\left(m-x-1\right)\times4+2\right]\left[a^2+\frac{i\left(i-1\right)}{2}\right]\right\}+\sum_{i=1}^{n}2mi\\&=m\left(2x+1\right)\left(\sum_{c=1}^{n}c^2-c\right)+m\left[\left(m-x-1\right)\times2+1\right]\left(\sum_{c=1}^{n}3c^2-c\right)+2m\left(\sum_{i=1}^{n}i\right)\\&=m\left(2x+1\right)\left[\frac{2n^3+3n^2+n}{6}-\frac{n\left(n+1\right)}{2}\right]+m\left[\left(m-x-1\right)\times2+1\right]\left[\frac{2n^3+3n^2+n}{2}-\frac{n\left(n+1\right)}{2}\right]+2m\frac{n\left(n+1\right)}{2}\\&=\frac{6m^2n^2+2mn-\left(4mn^3+6mn^2+2mn\right)x-\left(2m-6m^2\right)n^3}{3}\end{aligned}

注：\sum_{i=1}^{n}i^2 可用拉格朗日插值法计算出为 \frac{2n^3+3n^2+n}{6}，\pi 可用 acos(-1) 来计算。

直接计算即可，时间复杂度 O(1)。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, m, x, ans1, ans2, temp;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    if (m == 1) {
        ans2 = (4 * n * n * n + 3 * n * n - n) / 3;
        cout << ans2;
        return 0;
    }
    x = 1.0l * 2 * m / acos(-1);
    ans1 = (2 * n * n * n + 3 * n * n + n) * (x + 1) * x / 6;
    ans2 = (6 * m * m * n * n + 2 * m * n - (4 * m * n * n * n + 6 * m * n * n + 2 * m * n) * x - (2 * m - 6 * m * m) * n * n * n) / 3;
    cout << fixed << setprecision(20) << 1.0l * ans1 * acos(-1) + ans2;
    return 0;
}