欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  web前端

Codeforces #282 div 1 C Helping People 题解_html/css_WEB-ITnose

程序员文章站 2022-05-12 12:44:53
...
CF 282 C Helping People 题解

原题】不贴了。

废话】好久没写博客了。(我不会告诉你我是离线写的)于是来水经验来了。

来源简述】CF 282 C

原题简述】有N(10^5)个人,每个人有初始的钱。再给出M(5000)个操作L,R,P。每次表示L~R这些人有几率P(0

算法简述】首先把这些操作建立出树结构(可以借鉴线段树)。节点i表示范围Li~Ri,它的父亲一定包含它,它也包含它的所有子树。为了方便,建立一个L=1,R=N,P=0的无效节点作为根。

观察到M的范围小,我们用f[i][j]表示在节点i表示的范围内,加的钱数的期望(注意原先的钱数可以用RMQ计算出)。至于为什么是最多(注意还是前缀和性质)加了j元的期望。

那么tmp[j]= ∏f[son][mx[i]+j-mx[son]];

mx[o]是原先区间o的最大钱数。

(这里就用到了f的前缀和性质了)

注意到求完后做一步tmp[j]-=tmp[j-1],取消前缀和性质。

然后我们的任务是求出i的所有f值。

那么ans[i][j]=ans[i][j-1]+tmp[j-1]*p[i]+tmp[j]*(1-p[i]);

ans[i][j-1]:前缀和

tmp[j-1]*p[i]:由子树中得最大加j-1,且当前也加

tmp[j]*(1-p[i]):由子树中得最大加j,且当前不加

求完了所有的f[i][j]后,我们对于新加的点K,最后的ans满足

ANS=ans[m][0]*mx[m]+Σ (ans[m][i]-ans[m][i-1])*(mx[m]+i);

【*精华所得类似于分治的树形算法。

【代码】

#include#include#include#define N 100005#define M 5005using namespace std;struct arr{int l,r;double p;}a[M];int f[N][18],mx[N],used[N],n,i,j,T,m,k;double ans[M][M],tmp[M],ANS;inline int ask(int x,int y){  int len=(int)log2(y-x+1);  return max(f[x][len],f[y-(1=a[i].l&&a[j].r