自动搬运

查看原文

来自洛谷，原作者为

	Nuyoah_awa 事实证明，你没让我失望。

搬运于2025-08-24 22:52:11，当前版本为作者最后更新于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$ 的递推式：

$$f_i = f_{i-1} + (i-1) \times (2 \times m) \times 1 + g_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$。

答案求值

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

$$ans = \sum\limits_{i = 1}^{i \le n} 2m \times (f_i - g_i) + m \times g_i + i \times 2m (m > 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;
}