[BZOJ1011] [HNOI2008] 遥远的行星

题目链接,首先理解题意

有一条数轴,\([1,n]\)每个点上都有一个行星,每个行星\(i\)都有质量\(M_i\),同时有一个很小的实数常量\(A\);
当\(i,j\)两个行星有着\(i\leq Aj\)的关系时,\(i\)对\(j\)有着大小为\(\frac{M_i M_j}{j-i}\)的作用力,求每个星球受到的作用力大小

首先,按照题意模拟的复杂度是\(O(An^2)\)的,肯定会超时,考虑观察题面题解,发现\(A\)很小,可以瞎搞一搞

题目让我们对于每一个\(j\)求这个东西:$$\text{Ans}_j=\sum^{\lfloor Aj\rfloor}_{k=1}\frac{M_j M_k}{j-k}$$

然后发现\(\lfloor Aj\rfloor\)在\(j\)很大时依然很小,小到\(5\%\)的误差无所畏惧,所以可以瞎搞得到:$$\text{Ans}_j\approx\sum^{\lfloor Aj\rfloor}_{k=1}\frac{M_j M_k}{j-\frac{1}{2}\times\lfloor Aj\rfloor}$$

前缀和优化即可得到:设$\text{Sum}_i=\sum^{i}_{k=1}M_k$,有:$$\text{Ans}_j\approx\frac{\text{Sum}_{\lfloor Aj\rfloor}M_j}{j-\frac{1}{2}\times\lfloor Aj\rfloor}$$时间复杂度$O(n)$

代码
/*
 DOCUMENT NAME "20181128-bnds1011.cpp"
 CREATION DATE 2018-11-28
 SIGNATURE CODE_20181128_BNDS1011
 COMMENT [HNOI2008]遥远的行星
*/

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;

template<typename IntType>
void read(IntType& val) {
    val = 0;
    int c;
    bool inv = false;
    while (!isdigit(c = getchar()))
        if (c == '-')
            inv = true;
    do {
        val = (val << 1) + (val << 3) + c - '0';
    } while (isdigit(c = getchar()));
    if (inv)
        val = -val;
}

typedef long long ll;
const int MaxN = 1e5 + 10;

int n;
double a;
int m[MaxN];
ll sum[MaxN];


int main(int argc, char* argv[]) {

    read(n);
    scanf("%lf", &a);

    for (int i = 1; i <= n; i++) {
        read(m[i]);
        sum[i] = sum[i - 1] + m[i];
    }

    for (int i = 1; i <= n; i++) {
        int fl = i * a + 1e-7;
        if (i <= 1000) {
            double ans = 0;
            for (int j = 1; j <= fl; j++)
                ans += (double)m[j] * m[i] / (i - j);
            printf("%lf\n", ans);
        } else
            printf("%lf\n", (double)sum[fl] * m[i] / (i - .5*fl));
    }

    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注