[bzoj 1011] [HNOI2008]遥远的行星：近似算法（一种正确性显然的非乱搞的科学做法）

60 阅读 0 评论 40 点赞

我是靠谱客的博主奋斗火龙果，最近开发中收集的这篇文章主要介绍[bzoj 1011] [HNOI2008]遥远的行星：近似算法（一种正确性显然的非乱搞的科学做法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：给N个数Mi（1≤N≤10^5, 0≤Mi≤10^7）和实数a（0.01<a≤0.35），对每个1≤i≤N求 $sum_{j=1}^{ai}frac {M_iM_j} {i-j}$ ，相对误差不超过5%即可。

这种形式的和式不太好处理，也许用到某种奇妙的求和顺序、递推关系、或者数据结构？扫了一眼题解，黄学长的代码很短同时表示“这种题到底是什么鬼”，有题解标题为“根据所允许的误差进行模糊DP”。看来“误差不超过5%”的条件并不像我所以为的那样只是由于浮点误差……对于浮点误差而言，允许5%的相对误差似乎有点大？Too young, too simple, sometimes native……

于是又想了想。初中初识放缩法，对1/100+1/101+…+1/120这样的和式进行分组，组中的数用组内最大或最小的数替代，得出范围。组分多了难算，分少了范围太松，常常需要进一步调整。本题能不能运用这种思想呢？1/99999和1/100000相差并不大。

既然允许5%的误差是关键，那就来算一算。可以把答案调小，也可以调大，这里就调大好了。

设 $y > x$ ，则 $frac 1 y < frac 1 x$ ，为了用 $frac 1 x$ 代替 $frac 1 y$ ，须满足 $frac 1 x le (1+5%)frac 1 y iff y le 1.05x$

配合上前缀和，一段一段往前跳就好了。会跳多少次呢？y=1.05x，迭代一下，指数增长，所以分的段数是对数级别。这是一个时间复杂度 $O(nlg n)$ 的算法。牺牲了一点时间，但显然可以保证相对误差不超过5%。常数会不会很大呢？ $log_{1.05}10^5 approx 236$ ，总运算量在千万级别，可接受。

有一些其他做法，比如前2000个暴力算，后面的把分母统统当作i-ai/2，的确可以AC，但是……总感觉不太科学？

【UER #7】天路一道和相对误差有关的好题。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX_N = 1e5;
const double r = 1.05;
double M[MAX_N+1], S[MAX_N+1];

int main()
{
    int N;
    double a;
    scanf("%d %lf", &N, &a);
    for (int i = 1; i <= N; ++i)
        scanf("%lf", &M[i]);
    for (int i = 1; i <= N; ++i)
        S[i] = S[i-1] + M[i];
    for (int i = 1, j, k, p, q; i <= N; ++i) {
        double ans = 0;
        j = floor(i*a);
        while (j) {
            p = i-j;
            q = std::min((int)std::max(ceil(p*r), double(p+1)), i);
            k = i-q;
            ans += (S[j]-S[k])/p;
            j = k;
        }
        printf("%fn", ans*M[i]);
    }
    return 0;
}