HNOI2008 遥远的行星

发表于 | 分类于 |
字数统计: 421 字

题目链接

题解

看到数据规模就吓傻了
这题暴力是根本过不动的。
所以我们可以用一些玄学方法
在这题中，有一个很关键的提示：

误差不超过$5\%$即可

可以发现在这种条件下正确答案的范围非常宽
所以可以采用近似的方法，不必每一个$j-i$都计算，可以用一个值来代替某一个范围内的$j-i$。
具体的程序实现是：对于一个$j$，有编号为的行星给他力
将此区间分成$k$段，每段的分母$j-i$近似用该区间中点的分母表示
$k$可以自行选一个定值，这里用的是100。
可以往小里取，不TLE即可。

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
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
int n;
double a,m[100005],sum[100005],f[100005];
void init(){
    scanf("%d%lf",&n,&a);
    sum[0]=m[0]=0;
    for(int i=1;i<=n;i++)
        scanf("%lf",&m[i]),
        sum[i]=sum[i-1]+m[i];
}
void solve(){
    for(int i=1;i<=n;i++){
        double s=a*i,mid;
        int lim=floor(s);//[1,ai]
        if(lim<=100){//区间长不足100直接算
            for(int j=1;j<=lim;j++)
                f[i]+=m[i]*m[j]/(i-j);
        }else{
            int l2=lim/100;
            for(int j=l2;j<=l2*100;j+=l2)
                mid=(i-j+i-j+l2-1)*0.5,//算中点的分母
                f[i]+=(sum[j]-sum[j-l2])*m[i]/mid;
            for(int j=l2*100+1;j<=lim;j++)//不足100直接算
                f[i]+=m[i]*m[j]/(i-j);
        }
    }
    for(int i=1;i<=n;i++)
        printf("%.6lf\n",f[i]);
}
int main(){
    init();
    solve();
    return 0;
}