M_sea

洛谷3198 [HNOI2008]遥远的行星
LuoguBZOJ分析这种题。。。无话可说qwq题意不是很清楚,其实就是要求$\large ans[i]=\sum...
扫描右侧二维码阅读全文
08
2019/01

洛谷3198 [HNOI2008]遥远的行星

Luogu

BZOJ

分析

这种题。。。无话可说qwq

题意不是很清楚,其实就是要求$\large ans[i]=\sum\limits_{j=1}^{\lfloor i*a\rfloor}\frac{m[i]\times m[j]}{i-j}$。

注意到只要结果的相对误差不超过 5% 即可这句话。于是可以用一些奇淫技巧来乱搞。

随缘设一个常量$T$,不要太大(不然会$\mathrm{\color{blue}{TLE}}$),也不要太小(不然会$\mathrm{\color{red}{WA}}$)。

假设现在在计算$ans[i]$,设一个$x=\lfloor i*a\rfloor$,分两种情况处理:

  • $x\leq T$:直接暴力计算。
  • $x>T$:将$1$~$x$尽量平均地分成$T$段,第$i$段$[l_i,r_i]$的贡献近似为$\Large\frac{m[x]\times\sum_{j=l_i}^{r_i}m[j]}{i-(l_i+r_i)/2}$,然后累加。

然后就可以搞出这题了。复杂度大概是$O(nT)$的?

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

const int MAXN=100000+10;
const double EPS=1e-8;
const int T=10;

int n;
double a;
double m[MAXN];
double sum[MAXN];

int main() {
    scanf("%d%lf",&n,&a);
    for (re int i=1;i<=n;++i) scanf("%lf",&m[i]);
    for (re int i=1;i<=n;++i) sum[i]=sum[i-1]+m[i];
    for (re int i=1;i<=n;++i) {
        int x=i*a+EPS; double ans=0.0;
        if (x<=T) {
            for (re int j=1;j<=x;++j)
                ans+=m[j]*m[i]/(i-j);
        }
        else {
            int l=1,r,sz=x/T,rem=x%T;
            for (re int j=1;j<=T;++j,l=r+1) {
                r=l+sz-(j>rem);
                ans+=m[i]*(sum[r]-sum[l-1])/(i-(l+r)/2);
            }
        }
        printf("%.6f\n",ans);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 05 : 44 PM

发表评论