[jzoj 6087] [GDOI2019模拟2019.3.26] 获取名额解题报告 (泰勒展开+RMQ+精度)

题目链接：

题目：

题解：

只需要统计$\prod_{i=l}^r (1-\frac{a_i}{x})$
=$exp(\sum_{i=l}^r ln(1-\frac{a_i}{x}))(x>a_i)$
我们可以把$ln(1-x)|x<1|$泰勒展开，得到$-\sum_{i=1}^{∞}\frac{x^i}{i}=0-\frac{x}{1}-\frac{x^2}{2}-\frac{x^3}{3}-...$
那么里面化简得到$-\sum_{i=1}^{r} \sum_{j=1}^∞\frac{a_i^j}{x^j*j})=-\sum_{i=1}^∞\frac{1}{i*x^i}\sum_{j=l}^{r}a_j^i$
实测$∞$取$50$就可以，预处理前缀和来快速计算$\sum_{j=l}^{r}a_j^i$
注意把$x=x/max(a_i)$,$a_i=a_i/max(a_i)$，防止爆$double$的范围
但是发现精度会有很大问题
当$\frac{a_i}{x}$较大时，$ln$里面的东西会比较接近$0$，很难保证精度
为$\frac{a_i}{x}$设置一个$lim$，当$\frac{a_i}{x}>lim$时直接算，再递归左右区间
$lim$取$0.5$是可以过的
寻找区间内最大的$\frac{a_i}{x}$用$RMQ$
参考自大米饼大佬的博客

代码：

#include<bits/stdc++.h>

using namespace std;

typedef double db;

const int N=6e5+;

const int M=;

int n,q;

int bin[],lg[N],f[N][];

db res;

db a[N],s[M+][N];

inline char gc()

{

  static char*p1,*p2,s[];

  if(p1==p2)p2=(p1=s)+fread(s,,,stdin);

  return(p1==p2)?EOF:*p1++;

}

inline int read()

{

    char ch=gc();int s=;

    while (ch<''||ch>'') ch=gc();

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=gc();}

    return s;

}

int Max(int x,int y) {return a[x]>a[y]?x:y;}

void pre()

{

    for (int i=bin[]=;i<=;bin[i]=bin[i-]<<,i++);

    lg[]=-;

    for (int i=;i<=n;i++) f[i][]=i,lg[i]=lg[i>>]+;

    for (int i=;i<=;i++)

        for (int j=;j+bin[i]-<=n;j++)

            f[j][i]=Max(f[j][i-],f[j+bin[i-]][i-]);

}

int ask(int l,int r)

{

    int t=lg[r-l+];

    return Max(f[l][t],f[r-bin[t]+][t]);

}

db x;

db cal(int l,int r)

{

    db re=,t=;

    for (int i=;i<=M;i++)

    {

        t*=x;

        re-=(s[i][r]-s[i][l-])/(i*t);

    }

    return exp(re);

}

void solve(int l,int r)

{

    int mid=ask(l,r);

    if (a[mid]/x<0.5) {res*=cal(l,r);return;}

    res*=-a[mid]/x;

    if (l<mid) solve(l,mid-);

    if (r>mid) solve(mid+,r);

}

int main()

{

    freopen("orz.in","r",stdin);

    freopen("orz.out","w",stdout);

    n=read();q=read();

    db mx=;

    for (int i=;i<=n;i++) a[i]=read(),mx=max(mx,a[i]);

    for (int i=;i<=n;i++) a[i]/=mx;

    pre();

    for (int i=;i<=n;i++)

    {

        db t=;

        for (int j=;j<=M;j++)

        {

            t*=a[i];

            s[j][i]=s[j][i-]+t;

        }

    }

    while (q--)

    {

        int l=read(),r=read();

        x=read()/mx;

        res=;solve(l,r);

        printf("%.10f\n",-res);

    }

    return ;

}

巴特西

[jzoj 6087] [GDOI2019模拟2019.3.26] 获取名额解题报告 (泰勒展开+RMQ+精度)

题目链接：

题目：

题解：

代码：

最新文章

热门文章

巴特西

[jzoj 6087] [GDOI2019模拟2019.3.26] 获取名额 解题报告 (泰勒展开+RMQ+精度)

题目链接：

题目：

题解：

代码：

最新文章

热门文章

[jzoj 6087] [GDOI2019模拟2019.3.26] 获取名额解题报告 (泰勒展开+RMQ+精度)