[学习笔记]概率与期望

老师在讲概念时一直在摸鱼，可怜的我就做了几道题。。

跳一跳

一、题目

题目描述 现有一排方块，依次编号为 $1\dots n$。 方块 $1$ 上有一个小人，已知当小人在方块 $i$ 上时，下一秒它会等概率地到方块 $i$（即不动），方块 $i+1$，方块 $i+2$……方块 $n$ 上。 求小人到达方块 $n$ 所需要的期望时间（单位：秒）。 输出格式 若答案 $ans=\frac{A}{B}$ 输出 $A\times B^{-1}\mathrm{m}\mathrm{o}\mathrm{d}(10^9+7)$。其中 $B^{-1}$ 表示 $B\mathrm{m}\mathrm{o}\mathrm{d}(10^9+7)$ 下的逆元。 数据范围 对于 $100\%$ 的数据，$1⩽n⩽10^7$。

二、解法

作为我概率系统学习的第一道题，我就写的详细一些吧。😉 设$f[i]$为从$i$点出发到达$n$点的期望时间，则有： $f[i]=({\sum }_{j=i}^{n}f[j]+1)/(n-i+1)$ $\Rightarrow \frac{n-i}{n-i+1}f[i]=({\sum }_{j=i+1}^{n}f[j])/(n-i+1)+1$ $\Rightarrow f[i]=({\sum }_{j=i+1}^{n}f[j])/(n-i)+\frac{n-i+1}{n-i}$

有了这个递推式，我们从后向前推，维护一个$f$的和$sum$，就可以$O(n)$了，注意少开数组qwq。

#include <cstdio> #include <cstring> const int MOD = 1e9+7; const int MAXN = 1e7+5; int read() { int x=0,flag=1; char c; while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1; while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*flag; } int n,f,inv[MAXN],sum; void init() { inv[0]=inv[1]=1; for(int i=2; i<=n; i++) inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD; } signed main() { n=read(); init(); for(int i=n-1; i>=1; i--) { f=(1ll*sum*inv[n-i]+1ll*(n-i+1)*inv[n-i])%MOD; sum=(0ll+sum+f)%MOD; } if(f==0) puts("0"); else printf("%d\n",f); }

景区路线规划

一、题目

题目描述 游乐园被描述成一张 $n$ 个点，$m$ 条边的无向图（无重边，无自环）。每个点代表一个娱乐项目，第 $i$ 个娱乐项目需要耗费 $c_i$ 分钟的时间，会让小 y 和妹子的开心度分别增加 $h{1}_i$ , $h{2}_i$ ，他们俩初始的开心度都是 $0$ 。每条边代表一条路，第 $i$ 条边连接编号为 $x_i$ , $y_i$ 的两个娱乐项目，从 $x_i$ 走到 $y_i$ 或者从 $y_i$ 走到 $x_i$ 耗费的时间都是 $t_i$ 分钟。小 y 和妹子预计在游乐园里玩 $k$ 分钟。最开始的时候，小 y 和妹子会等概率的随机选择一个娱乐项目开始玩，每玩完一个项目后，小 y 和妹子会等概率的随机选择一个可以从当前项目直达的且来得及玩的项目作为下一个项目。如果玩完一个项目后周围没有可以直达的且来得及玩的项目，小 y 和妹子就会提前结束游玩。请你分别计算小 y 和妹子在游玩结束后开心度的期望。 输入格式 第一行给出三个空格隔开的整数，分别表示 $n,m,k$ 接下来的 $n$ 行，每行三个空格隔开的整数，分别表示 $c_i,h{1}_i,h{2}_i$ 接下来的 $m$ 行，每行三个空格隔开的整数，分别表示 $x_i,y_i,t_i$ 输出格式 两个用空格隔开的实数，分表表示小 y 和妹子开心度的期望，精确到小数点后 $5$ 位。 数据范围

$0<n\le 100,1\times 60\le k\le 8\times 60$ - $10\le c_i\le 60,0<h{1}_i,h{2}_i\le 100$ - $0<t_i\le 15$

二、解法

这道题求期望，直接搜索。😉 我们搜索需要什么，需要当前点是什么和现在的时间，把他们塞进记忆化搜索的数组里面就行了。

#include <cstdio> int read() { int x=0,flag=1; char c; while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1; while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*flag; } int n,m,k,tot,f[105]; double w[105],h1[105],h2[105]; struct node { double f,g; node operator + (const node &R) const { return node{f+R.f,g+R.g}; } } ans,dp[105][505]; struct edge { int v,c,next; } e[10005]; node dfs(int u,int t) { if(dp[u][t].f!=-1) return dp[u][t]; node tmp=node{0,0}; double cnt=0; for(int i=f[u]; i; i=e[i].next) { int v=e[i].v,c=e[i].c; if(t>=c+w[v]) { tmp=tmp+dfs(v,t-c-w[v]); tmp.f+=h1[v]; tmp.g+=h2[v]; cnt+=1.0; } } if(cnt)tmp.f/=cnt,tmp.g/=cnt; return dp[u][t]=tmp; } int main() { n=read(); m=read(); k=read(); for(int i=1; i<=n; i++) scanf("%lf %lf %lf",&w[i],&h1[i],&h2[i]); for(int i=1; i<=m; i++) { int u,v,c; u=read(); v=read(); c=read(); e[++tot]=edge{v,c,f[u]},f[u]=tot; e[++tot]=edge{u,c,f[v]},f[v]=tot; } for(int i=1; i<=n; i++) for(int j=0; j<=k; j++) dp[i][j]=node{-1,-1}; for(int i=1; i<=n; i++) { ans=ans+dfs(i,k-w[i]); ans.f+=h1[i]; ans.g+=h2[i]; } printf("%.5lf %.5lf\n",ans.f/n,ans.g/n); }

换教室

一、题目

点此看题

二、解法

终于有了一道要脑子的期望题 ，它竟然要求期望的最小值？ 其实也没有多可怕，我们考虑每个换课操作带来的影响，发现只会对前后的路径造成影响，于是就可以定义$dp[i][j][0/1]$表示当前点 换$/$不换，一共尝试换了$j$节课，我们把所有的可能乘上发生这个可能的概率求和就是期望了，然后当普通$dp$来写就行了。 一开始要预处理出每两个点间的最短路，注意要判重边和自环，可以用滚动数组优化。😉

#include <cstdio> #include <cstring> #include <iostream> #define inf 0x3f3f3f3f using namespace std; const int MAXN = 2005; int read() { int x=0,flag=1;char c; while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1; while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*flag; } int n,m,v,e,c[MAXN],d[MAXN]; int G[305][305]; double ans,k[MAXN],dp[MAXN][MAXN][2]; int main() { n=read();m=read();v=read();e=read(); for(int i=1;i<=n;i++) c[i]=read(); for(int i=1;i<=n;i++) d[i]=read(); for(int i=1;i<=n;i++) scanf("%lf",&k[i]); memset(G,0x3f,sizeof G); for(int i=1;i<=v;i++) G[i][i]=0; for(int i=1;i<=e;i++) { int u=read(),v=read(),c=read(); G[u][v]=G[v][u]=min(G[u][v],c); } for(int k=1;k<=v;k++) for(int i=1;i<=v;i++) for(int j=1;j<=v;j++) { if(G[i][k]+G[k][j]<G[i][j]) G[i][j]=G[i][k]+G[k][j]; } for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j][0]=dp[i][j][1]=inf; dp[1][0][0]=dp[1][1][1]=0; for(int i=2;i<=n;i++) { dp[i][0][0]=dp[i-1][0][0]+G[c[i-1]][c[i]]; for(int j=1;j<=min(i,m);j++) { dp[i][j][0]=min(dp[i-1][j][0]+G[c[i-1]][c[i]],dp[i-1][j][1]+G[c[i-1]][c[i]]*(1-k[i-1])+G[d[i-1]][c[i]]*k[i-1]); dp[i][j][1]=min(dp[i-1][j-1][0]+G[c[i-1]][d[i]]*k[i]+G[c[i-1]][c[i]]*(1-k[i]),dp[i-1][j-1][1]+G[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+G[c[i-1]][d[i]]*(1-k[i-1])*k[i]+G[d[i-1]][c[i]]*k[i-1]*(1-k[i])+G[d[i-1]][d[i]]*k[i-1]*k[i]); } } ans=inf; for(int i=0;i<=m;i++) ans=min(ans,min(dp[n][i][0],dp[n][i][1])); printf("%.2lf\n",ans); }

单选错位

一、题目

点此看题

二、解法

这道题一开始想写类似数位$dp$的搜索，发现数据范围是在是太大了，所以$gg$了。 这道题要利用期望的一个性质，也就是可加性，又称线性性，所以我们就可以考虑每道题的期望得分然后求和，每个题的期望得分是$\frac{min(a[i],a[i-1])}{a[i]\times a[i-1]}$也就是$1/max(a[i],a[i-1])$，要特判$i=1$的情况。

#include <cstdio> #include <iostream> using namespace std; const int MAXN = 10000005; int read() { int x=0,flag=1;char c; while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1; while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*flag; } int n,A,B,C,a[MAXN]; double ans; int main() { scanf("%d %d %d %d %d",&n,&A,&B,&C,a+1); for(int i=2;i<=n;i++) a[i]=((long long)a[i-1]*A+B)%100000001; for(int i=1;i<=n;i++) a[i]=a[i]%C+1; ans+=1.0/max(a[1],a[n]); for(int i=2;i<=n;i++) ans+=1.0/max(a[i],a[i-1]); printf("%.3lf",ans); }