题目链接: BZOJ - 1011

题目分析

这道题的特别之处在于,答案可以有5%的误差。

嗯..So? 我还是不会,于是看题解。

神犇的题解就是利用这误差范围求一个近似解。

怎么求近似解呢?假如 g[i] 是第 i 个点受到的引力来源中最后的一个点。那么我们如果要直接求 f[i] (第i个点受到的引力)是要枚举 1 到 g[i] 。

然而如果我们直接从之前的一个 f[i - t] 为基础近似一下,再暴力计算 g[i - t] + 1 到 g[i] 的部分,就会大大节省时间了。

因为离得越远的行星带来的引力越小,所以 1 到 g[i - t] 的行星近似一下之后对 f[i] 答案的误差并不会很大。

怎么来近似呢?某位神犇推了如下公式:

[BZOJ 1011] [HNOI2008] 遥远的行星 【近似解】-LMLPHP

[BZOJ 1011] [HNOI2008] 遥远的行星 【近似解】-LMLPHP

其中 t 的取值越大,用时越长,但误差越小。我的代码中取了 t=100,但是经过试验,我这个代码改成 t=15 在BZOJ上依然可以 AC 。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std; const int MaxN = 100000 + 5, t = 100; typedef double DB; int n;
int W[MaxN], g[MaxN]; DB A, Ans;
DB f[MaxN]; int main()
{
scanf("%d%lf", &n, &A);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &W[i]);
g[i] = (int)(A * i + 1e-8);
}
for (int i = 1; i <= n; ++i)
{
if (i <= t)
{
f[i] = 0.0;
for (int j = 1; j <= g[i]; ++j)
f[i] += (DB)W[j] / (DB)(i - j);
f[i] *= (DB)W[i];
}
else
{
f[i] = f[i - t] / (DB)W[i - t] * ((DB)(i - t) - (DB)g[i - t] / 2.0) / ((DB)(i) - (DB)g[i - t] / 2.0);
for (int j = g[i - t] + 1; j <= g[i]; ++j)
f[i] += (DB)W[j] / (i - j);
f[i] *= (DB)W[i];
}
printf("%.8lf\n", f[i]);
}
return 0;
}

  

05-11 10:57