kuangbin专题 概率期望DP总结

题目链接: https://vjudge.net/contest/76505#overview

---

A- A Dangerous Maze LightOJ - 1027 题意: 现在在你面前有N个门。每个门要么把你传送出迷宫，要么把你传送来的位置且你的记忆也会回到初始的时候。现在给出每个门传送的时间t，若t为正数，说明该门花费时间t可以将你传送出迷宫，若 t 为负数，说明该门花费时间 t 将你传送到原来的位置。已知你选择每个门的概率是相同的，问你出迷宫所花费时间的期望。输出结果写出分数形式，且分子分母互质，若不能出迷宫输出inf。 思路: 设期望为E,正数的门权值为sum1,负数的门权值为sum2,则 $$E=\frac{sum1}{n}+\frac{sum2+cnt\ast E}{n}$$ 化简之后$$E=\frac{sum}{n-cnt}$$

---

B - Discovering Gold LightOJ - 1030 题意: 现在有n个格子，每个格子上都有一定的黄金值；还有一个色子（1-6）。起始位置站在格子1上面，若每次投掷色子得到数x,x+i<=n（i表示现处位置的格子编号），则可以到达（x+i）格子上；反之，再进行一次投掷。问：到达标号为n的格子上面，得到黄金的期望值是多少？ 思路: 正所谓概率正求，期望反推 设dp[ i ]为在i点的期望，则$$dp[i]=\frac{{\sum }_{j=1}^{6}dp[i+j]}{6}$$ dp[ n ]=a[ n ]; O(6n)递推可得dp[ 1 ]就是所求答案

---

C - Race to 1 Again LightOJ - 1038 题意: 要求将一个数变成1，每次可以除去它的任意一个因子，问你次数的期望。 思路: 从1反推，预处理每个数的因子数cnt， $$dp[x]=\frac{{\sum }_{i|d}(dp[i]+1)}{cnt}(i为x的因子)$$ 复杂度O( n*sqrt( n ) )

---

D - Just another Robbery LightOJ - 1079 思路： 概率01背包

---

E - Birthday Paradox LightOJ - 1104 题意: 一年有n天，问当有多少人的时候，人中两人生日概率相同达到1/2以上。 思路: 经典生日悖论问题，正难易反，等价于求生日不同的概率在1/2以下

---

F - Snakes and Ladders LightOJ - 1151 题意: 在1-n的格子里，你每次投骰子前进，但有的格子会传送到其他的格子，现在已知起点与终点没有传送门，请问到达n点的投的期望次数 思路: 高斯消元经典题目，我们可以列出式子 $$若是有传送门的，则dp[x]=dp[nxt[x]]$$

$$反之，则dp[i]=\frac{1}{6}\ast \sum _{j=1}^{k}dp[i+j]+\frac{1}{6}\ast \sum _{j=k+1}^{6}dp[i]+1$$

化简得$$k\ast dp[i]-\sum _{j=1}^{k}dp[i+j]=6$$ 若是超过投的数超过100，则再投一次，因为存在环没有递推性所以运用高斯消元

---

G - Dice (III) LightOJ - 1248 题意: 有一个n面的骰子，问每个面都出现一次的期望次数 思路: 解法一 $$dp[n]=1,dp[i]=\frac{n-i}{n}\ast dp[i+1]+\frac{i}{n}\ast dp[i]+1$$ 解法二 因为在几何分布的中，概率的倒数是期望，故$$ans=1+（n/n-1）+（n/n-2）+\dots \dots +n$$

---

H - Island of Survival LightOJ - 1265 题意: 人遇到老虎会死，老虎遇到老虎，两只老虎都死，人遇得到鹿不会死，鹿遇到老虎会死，鹿遇到鹿不会死，给d只鹿，n只老虎，问人生存的概率 思路: 若没有老虎，则人的生存率为1，若老虎的数量为奇数，则人的生存率为0，接下来我们来考虑一下老虎数量为偶数，人的生存率等价于老虎两俩相遇的概率。则 $$(C_n^2\ast C_{n-2}^2\ast \dots \dots \ast C_2^2)/(C_{n+1}^2\ast C_{n-1}^2\dots \dots \ast C_3^2)=1/(n+1)$$

---

I - Beating the Dataset LightOJ - 1274 题意: 设为X，Y。题目可以抽象为某个01串全排列该位置与前一个位置不同或者第一位为0的数量期望。 思路: 解法一，考虑各个位的贡献，每个1贡献的期望是各个0在它前面或者后面两种所以是2 * X * Y，每个0额外贡献了处在第一位期望也就是Y。

所以得出$$公式：ans=(2\ast X\ast Y+Y)/(X+Y)$$ 解法二，三维dp滚动，注意细节，很容易犯错 设dp[ i ] [ j ] [ 1/0 ]前i位含有j个1，当前位是0或1

memset(dp,0,sizeof dp); for(int i=n-1;i>=0;i--) { cnt^=1; double p1,p2; for(int j=min(x,i);j>=0&&i-j<=y;j--) { p1=(x-j)*1.0/(n-i);//选取1的概率 p2=(y-i+j)*1.0/(n-i);//选取0的概率 dp[cnt][j][0]=dp[cnt^1][j+1][0]*p1+(dp[cnt^1][j][1]+1)*p2; dp[cnt][j][1]=(dp[cnt^1][j+1][0]+1)*p1+dp[cnt^1][j][1]*p2; } }

---

J - Lights inside 3D Grid LightOJ - 1284 题意: 给你长宽高x,y,z的长方体,则在k次随机选两个点，所有在x1<=x<=x2,y1<=y<=y2,z1<=z<=z2，都被选一次，问最后灯开着的状态 思路: 考虑点的贡献和就是总贡献,每个点各维被选中的概率$$px=1-((m-x)\ast (m-x)+(x-1)(x-1))/(m\ast m)$$ $$p=px\ast py\ast pz$$ 假设选取n次，f(n)为选取n次被选中奇数次的概率，g(n)为选区n次被选中偶数次的概率

f(n)=p*g(n-1)+(1-p)*f(n-1)

g(n)=p*f(n-1)+(1-p)*g(n-1)

f(n)+g(n)=1

得f(n)=(1-2p)*f(n-1)+p，f(1)=p

展开后为f(n)=(1-2p)^ (n-1)*p+ (1-2p)^(n-2)*p+…+(1-2p)*p+p

就是一个等比数列，第一项为p，用等比求和公式得f(n)=0.5-0.5*(1-2p)^n

f(n)就是这个点灯亮的期望

---

K - Where to Run LightOJ - 1287: 题意: 有一个小偷要遍历n个城市，每个城市只能走一次，在一个城市他可以选择在这等待5分钟或者选择下一个城市(条件是这下一个城市能把剩下的城市都走完)走，选择某下一个城市与当前停留在原点是等概率的，求遍历完整个图的期望时间。 思路: 记忆化搜索，状压dp，细节很多，容易写错

#include<bits/stdc++.h> using namespace std; const int maxn=16; int mp[maxn][maxn]; bool vis[1<<maxn][maxn],canReach[1<<maxn][maxn]; double dp[1<<maxn][maxn]; int n,m; bool dfs(int S,int u) { if(S==(1<<n)-1) return dp[S][u]=0,true; if(vis[S][u]) return canReach[S][u]; vis[S][u]=1; int cnt=0; double sum=0; for(int v=0;v<n;v++) { if(!mp[u][v]||(S&(1<<v))) continue; if( dfs(S|(1<<v),v) ) { canReach[S][u]=true; sum+=dp[S|(1<<v)][v]+mp[u][v]; cnt++; } } if(!canReach[S][u]) return dp[S][u]=0,false; return dp[S][u]=(5.0+sum)/cnt,true; } int main() { int T; scanf("%d",&T); int cas=1; while(T--) { scanf("%d%d",&n,&m); memset(mp,0,sizeof mp); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); mp[u][v]=mp[v][u]=w; } memset(vis,false,sizeof vis); memset(canReach,false,sizeof canReach); dfs(1,0); printf("Case %d: %.7f\n",cas++,dp[1][0]); } return 0; }

M - Sending Packets LightOJ - 1321 题意: 给定一张无向图，每条边都有一个通过的概率 ，如果无法通过，那么就要回到起点重新出发。从起点到终点的时间固定为K，如果成功到达，又需要额外花费K的时间，问传送S次的最小期望时间 思路: 解法一 最大成功率为p，$$E=(1-p)\ast (E+2k)+p\ast 2k$$ 解得$$E=2k/p\ast s$$ 解法二 因为最小时间的期望， 即最大的传输成功率， 最小的传输次数， 即只传输成功一次所需要的时间的期望。 我们所要求的是传输成功一次需要的次数的期望， 这满足几何分布， E = 1 / p。 　　所以，ans = E * 2 * K * S

---

N - Aladdin and the Magical Sticks LightOJ - 1342 题意: 有 N根棍子，每根棍子都有一个权值,其中有若干根可识别的，若干根不可识别的,抽到了可识别的棍子，就不放回，抽到了不可识别的，就要放回 问所有棍子都至少被抽过一次后的期望权值和 思路: 某位大佬的题解 https://www.cnblogs.com/By-ruoyu/archive/2015/08/12/4725554.html 师兄的题解

---

O - Expected Cards LightOJ - 1364 题意: 一副标准的扑克牌，有四种不同花色，每个花色有13张牌，还有两张大小王，一共54张牌，随机打乱后，背面朝上放置在桌上，然后你一张一张的去翻，如果翻到大小王，你需要马上让大小王变成四种花色中的一种，给你a，b，c，d四个整数对应所需要翻出的四种花色的最少牌数，问最小期望是多少次。 思路: 记忆化搜索，高维dp，记得每一轮都要加1，因为都要抽取一张 假设dp[a][b][c][d][e][f] 表示此时已经翻出的前面四种花色的牌数对应分别为a，b，c，d以及大小王所变对应的花色e，f时到达目标状态还需翻牌的期望次数

#include<bits/stdc++.h> using namespace std; #define inf 1e9 double dp[14][14][14][14][5][5]; int num[5]; int check(int a,int b,int c,int d,int p,int q)//判断是不是各种牌都满足要取的数量了 { int x[5]={0}; x[1]=a;x[2]=b;x[3]=c;x[4]=d; x[p]++;x[q]++; for(int i=1;i<=4;i++) if(x[i]<num[i]) return 0; return 1; } double dfs(int a,int b,int c,int d,int p,int q) { if(check(a,b,c,d,p,q)) return dp[a][b][c][d][p][q]=0; if(dp[a][b][c][d][p][q]>=0) return dp[a][b][c][d][p][q]; int sum=54-a-b-c-d; if(p) sum--; if(q) sum--; if(sum==0) return 0; double ans=0.0; if(a<13) ans+=dfs(a+1,b,c,d,p,q)*(13-a)/sum;//下一张取a种牌的期望 if(b<13) ans+=dfs(a,b+1,c,d,p,q)*(13-b)/sum; if(c<13) ans+=dfs(a,b,c+1,d,p,q)*(13-c)/sum; if(d<13) ans+=dfs(a,b,c,d+1,p,q)*(13-d)/sum; if(p==0) { double tmp=inf; for(int i=1;i<=4;i++) tmp=min(tmp,dfs(a,b,c,d,i,q));//因为大小王是人为规定的当哪张牌使，所以取最小的 ans+=tmp/sum; } if(q==0) { double tmp=inf; for(int i=1;i<=4;i++) tmp=min(tmp,dfs(a,b,c,d,p,i)); ans+=tmp/sum; } ans+=1.0;//本次取一张牌 return dp[a][b][c][d][p][q]=ans; } int t,cas=0; int main() { scanf("%d",&t); while(t--) { for(int i=1;i<=4;i++) scanf("%d",&num[i]); int delt=0; for(int i=1;i<=4;i++) delt+=max(num[i]-13,0);//判断让取的牌是否合理 if(delt>2) { printf("Case %d: -1\n",++cas); continue; } memset(dp,-1,sizeof dp); double ans=dfs(0,0,0,0,0,0); printf("Case %d: %.8lf\n",++cas,ans); } return 0; }

---

P - A Dangerous Maze (II) LightOJ - 1395 题意: A题的加强版，改为若进去过负值门，则能记住后K个负值门后不会再选，问出去的期望值 思路: 大佬题解 https://www.cnblogs.com/jiachinzhao/p/7210159.html

---

Q - Batting Practice LightOJ - 1408 题目: 每次投球投偏的概率为p，如果连续投中k1次或者连续投偏k2次则投球结束，问投球个数的期望值 思路: 大佬题解 https://blog.csdn.net/dsaghjkye/article/details/83178393