[bzoj1011][HNOI2008]遥远的行星


[bzoj1011][HNOI2008]遥远的行星

标签: 乱搞


题目链接

扯淡

真的是一道神题........

题解

这道题直接模拟是\(O(n^2)\)的。
\[设g_i=\lfloor aAi \rfloor\]
\[f[i]=\sum_{j=1}^{g_i} {w[i]×w[j] \over {i-j}} \]
然而由于除数的限制不能够直接优化。
如果能把分母变成同一个数,那么问题就很简单了。
注意到5%的误差其实只与分母有关。
由于a很小,那么\(g_i\)也很小
假如把分母都取成\(i- \frac {g_i} 2\),那么误差是\(\frac 1 i\)级别的。
所以对于小数据可以直接暴力,大数据就把分母都当成$i- \frac {g_i} 2 O(1)算 $。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
inline int read()
{
    int sum=0,p=1;char ch=getchar();
    while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
    if(ch=='-')p=-1,ch=getchar();
    while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
    return sum*p;
}

const int T=2000;
const int maxn=1e5+20;
int n,w[maxn];
ll sum[maxn];
double A;

void init()
{
    n=read();cin>>A;
    REP(i,1,n)w[i]=read();
}
const double eps=1e-8;
void doing()
{
    REP(i,1,n)
    {
        double ans=0;
        int k=(int)(eps+(i*A));
        if(i<=T)
        {
            REP(j,1,k)ans+=(double)w[j]*w[i]/(i-j);
        }else
        {
            ans=((double)sum[k]*w[i])/(i-(double)k/2);
        }
        sum[i]=sum[i-1]+w[i];
        printf("%.6lf\n",ans);
    }
}

int main()
{
    init();
    doing();
    return 0;
}

作者:Deadecho,发布于:2018/08/29
原文:https://www.cnblogs.com/gzy-cjoier/p/7503578.html