Codeforces#282div1CHelpingPeople題解_html/css

【原題】不貼了。

【廢話】好久沒寫博客了。（我不會告訴你我是離線寫的）于是來水經驗來了。

【來源簡述】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<=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);}

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com