P9827 [ICPC2020 Shanghai R] Sky Garden 题解

Nuyoah_awa · 2023-11-08 22:16:36 · 题解

题解区目前都是 \mathcal O(n^3) 的做法，但是我觉得 \mathcal O(n) 的挺好想的，来写发 \mathcal O(n) 的题解。

题目大意

有 n 个半径为 1\sim n 的同心圆，且有 m 条过圆心直线将圆平分。

对于所有线与圆的交点，从中任取两个，求两点最短路的和。

题目分析

我们不难发现，每个圆上有 2m 个点，一共 n 个圆，很容易想到 DP，并且在圆上有对称性，对于每个圆，我们其实只需要算出一个点的贡献，剩下的可以根据对称性得到。

DP 大体思路

首先，我们规定圆根据半径从小到大编号为 1 \sim n。

我们设 f_i 表示第 i 个圆上一点到第 1 \sim i 个中所有点的最短路和。

对于每个 f_i，我们分成同层与不同层两种情况得出。

DP 转移

对于这个点与本层的点的最短路，不难发现，要么通过圆上走来，要么通过半径走来，每个点的最短路通过两值取较小得出，如下图。

对于这个点 x 与半径更小的圆上的点 y，我们观察下图，发现两中路径中，先从 y 到 x 所在的圆上，然后再从这个点到 x 与先从 y 到 y 所在的圆上 x 对应的点，然后再到 x相比，很明显后者更优，原因如下：

首先，我们发现，如果在较小的圆中，这两点的最短路径是从圆上走的，那么另一个圆对应的两点也是从圆上走的，反之同理。于是，我们可以分为两类讨论：

1. 两点从圆上走，观察下图，很明显蓝色更优，因为半径更小的弧长也更小。

2. 下图中，两点从半径走，则蓝色更优，因为他没必要先向外走再走回来。

综上，我们先从 y 走到 x 对应的点，然后通过半径的一段走到 x。

于是，我们可以得到 f_i 的递推式：

其中，g_i 表示一个点到这个圆上的点的距离和。根据以上分析，g_i 是通过枚举得来的，但是，我们发现根据上述的两类讨论可以得出“如果在较小的圆中，这两点的最短路径是从圆上走的，那么另一个圆对应的两点也是从圆上走的，反之同理。”也就是说 g_i 也可以递推得出。

又经过观察发现，g_i 其实都可以 \mathcal O(1) 求出，即 g_i = i \times g_1，其中 g_1 通过枚举得出。

边界状况

首先，对于 g_1，g_1 = \sum\limits_{i = 0}^{i \le 2m} \min\{2 , \dfrac{i}{2m} \times 2π, \dfrac{2m - i}{2m} \times 2π\}。

根据圆的轴对称性，式子可化简为 g_1，g_1 = (\sum\limits_{i = 0}^{i < m} \min\{2 , \dfrac{i}{2m} \times 2π\}) \times 2 + 2。

而对于 f_1，没有半径比其小的圆，所以 f_1 = g_1。

答案求值

答案依旧可以分为两部分算，原理同上，式子为：

所以时间复杂度为 \mathcal O(m) 预处理，\mathcal O(n) 递推，\mathcal O(n) 求答案。总时间复杂度是 \mathcal O(n) 的。

code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define int long long
#define double long double

using namespace std;

const int N = 505;
int n, m;
double ans = 0, f[N], g[N], tmp, pi = 3.141592653589;

signed main()
{
    scanf("%lld %lld", &n, &m);
    for(int i = 1;i < m;i++)
        tmp += min(i * pi / m, 2.0L);
    tmp *= 2;
    tmp += 2;
    f[1] = g[1] = tmp;
    for(int i = 2;i <= n;i++)
    {
        g[i] = g[1] * i;
        f[i] = f[i-1] + 2 * m * (i - 1) + g[i];
    }
    for(int i = 1;i <= n;i++)
        ans += 2 * m * (f[i] - g[i]) + m * g[i] + (m > 1 ? 2 * m * i : 0);
    printf("%.10Lf", ans);
    return 0;
}