题解：P9827 [ICPC2020 Shanghai R] Sky Garden

原题链接

• 洛谷 P9827 [ICPC2020 Shanghai R] Sky Garden

解题思路

@Nuyoah_awa 的 题解 提供了 $O(n)$ 的做法。观察发现其代码中的 DP 是线性的，经过整理可以 $O(1)$ 实现。

$$O(n^3)\to O(1)$$

令：

$$t=\left\lfloor\frac{2m}{\pi}\right\rfloor$$

则：

$$p=\frac{t(t+1)\times n(n+1)(2n+1)}{6}$$ $$q=\frac{mn(n+1)(6mn-4tn-2t-2n-1+3\times[m\not=1])}{3}$$ $$S=p\pi+q$$

至此，已成艺术。

接下来看看人工队的表现。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const double pi=acos(-1);
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll n,m;
	cin>>n>>m;
	ll t=m*2/pi;
	ll p=t*(t+1)*n*(n+1)*(n*2+1)/6;
	ll q=m*n*(n+1)*(m*n*6-t*n*4-t*2-n*2-1+(m>1)*3)/3;
	cout<<fixed<<setprecision(12)<<p*pi+q<<'\n';
	return 0;
}