Codeforces#282div1CHelpingPeople题解_html/css_WEB-ITnose
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Codeforces#282div1CHelpingPeople题解_html/css_WEB-ITnose,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2611字,纯文字阅读大概需要4分钟。
内容图文
CF 282 C Helping People 题解【原题】不贴了。
【废话】好久没写博客了。(我不会告诉你我是离线写的)于是来水经验来了。
【来源简述】CF 282 C
【原题简述】有N(10^5)个人,每个人有初始的钱。再给出M(5000)个操作L,R,P。每次表示L~R这些人有几率P(0<=P<=1)给他们每人一元。求最后所有人钱数最大值的期望。
【算法简述】首先把这些操作建立出树结构(可以借鉴线段树)。节点i表示范围Li~Ri,它的父亲一定包含它,它也包含它的所有子树。为了方便,建立一个L=1,R=N,P=0的无效节点作为根。
观察到M的范围小,我们用f[i][j]表示在节点i表示的范围内,加的钱数<=j的期望(注意原先的钱数可以用RMQ计算出)。至于为什么是<=,因为后面要用到前缀和??反正f算的时候再前缀和一下。那么到节点i,我们开一数组tmp[j]表示所有子树中影的最多(注意还是前缀和性质)加了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<<len)+1][len]);}inline int cmp(const arr &a,const arr &b){return a.r-a.l<b.r-b.l;}int main(){ scanf("%d%d",&n,&m); for (i=1;i<=n;i++) scanf("%d",&f[i][0]); for (j=1;j<=17;j++) for (i=1;i<=n;i++) T=i+(1<<(j-1)),f[i][j]=max(f[i][j-1],(T<=n)?f[T][j-1]:0); for (i=1;i<=m;i++) scanf("%d%d%lf",&a[i].l,&a[i].r,&a[i].p); a[++m]=(arr){1,n,0}; sort(a+1,a+m+1,cmp); for (i=1;i<=m;i++) { mx[i]=ask(a[i].l,a[i].r); for (k=0;k<=m;k++) tmp[k]=1.0; for (j=1;j<i;j++) if (a[j].l>=a[i].l&&a[j].r<=a[i].r&&!used[j]) { used[j]=1; for (k=0;k<=m;k++) if (mx[i]+k-mx[j]<=m) tmp[k]*=ans[j][mx[i]+k-mx[j]]; } for (k=m;k;k--) tmp[k]-=tmp[k-1]; ans[i][0]=(1-a[i].p)*tmp[0]; for (k=1;k<=m;k++) ans[i][k]=ans[i][k-1]+tmp[k-1]*a[i].p+tmp[k]*(1-a[i].p); //ans[i][k-1]:加上k-1的期望(ans[i]实质是前缀和性质) //tmp[k-1]*p[i]:由子树中得最大加k-1,且当前也加 //tmp[k]*(1-p[i]): 由子树中得最大加k,且当前不加 } ANS=ans[m][0]*mx[m]; for (i=1;i<=m;i++) ANS+=(ans[m][i]-ans[m][i-1])*(mx[m]+i); printf("%.10lf",ANS);}
内容总结
以上是互联网集市为您收集整理的Codeforces#282div1CHelpingPeople题解_html/css_WEB-ITnose全部内容,希望文章能够帮你解决Codeforces#282div1CHelpingPeople题解_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。