「HNOI2008」遥远的行星

发表于 | 分类于 | | 浏览量： 次

又是一道玄学的题目QwQ。

传送门

洛谷P3198

BZOJ1011

题解

首先要一眼看到这题的重点：结果的相对误差不超过$5\%$即可。

所以考虑非完美算法。

首先，对于第$i​$个行星，对它有贡献的星球区间是$[1,\lfloor A\cdot i\rfloor]​$。设$R=\lfloor A\cdot i\rfloor​$。

然后再设一个阈值$S$比如$S=n^{0.4}$。

接下来的操作类似于分块，把区间$[1,R]$分成若干个块，每个块的大小为$S$，剩下的零头暴力搞，对于每一个完整的块，设这个块为$[a,b]$，那么这个块的贡献约等于

这个式子可以构造前缀和来求。

把所有块的贡献加起来，注意下细节，就能过了QwQ。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100005;
int n,S,M[maxn];double A,ans;LL sum[maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
int main()
{
	n=read();scanf("%lf",&A);S=pow(n,0.38)+1e-10;
	for(int i=1;i<=n;i++){M[i]=read();sum[i]=sum[i-1]+M[i];} //构造前缀和
	for(int i=1;i<=n;i++)
	{
		int R=i*A+1e-10,j;ans=0;   //加上1e-10是为了防止精度损失
		for(j=1;j+S<=R;j+=S)    //处理整块
			ans+=(double)M[i]*(sum[j+S-1]-sum[j-1])/(i-(double)(2*j+S-1)/2);
		for(;j<=R;j++)      //处理零头
			ans+=(double)M[i]*M[j]/(i-j);
		printf("%lf\n",ans);
	}
	return 0;
}