Day2:期望DP
A - CF148D Bag of mice
设 \(dp_{i,j}\) 表示还剩下 \(i\) 只白鼠,\(j\) 只黑鼠 A 的胜率。
- 大家都没有拿到白鼠,那么 B 赢,\(dp_{0,0}=0\)。
- 没有白鼠了,那么 B 赢,\(dp_{0,j}=0\)。
- 全是白鼠了,那么 A 赢(A 先抓),\(dp_{i,0}=1\)。
然后转移,有这几种情况:
- 第一次就抓到白鼠:\(dp_{i,j}=\frac{i}{i+j}\)。
- A 抓到黑鼠,B 抓到黑鼠,跑出来白鼠:\(dp_{i,j}=dp_{i-1,j-2}\times\frac{j}{i+j}\times\frac{j-1}{i+j-1}\times\frac{i}{i+j-2}\)(三个分数表示跑出这三种鼠的概率)
- A 抓到黑鼠,B 抓到黑鼠,跑出来黑鼠:\(dp_{i,j}=dp_{i,j-3}\times\frac{j}{i+j}\times\frac{j-1}{i+j-1}\times\frac{j-2}{i+j-2}\)(三个分数表示跑出这三种鼠的概率)
- 其他情况 A 都是输掉的,不用管他。
注意 2,3 两种情况对于剩余的黑白老鼠数量有要求。
#include <bits/stdc++.h>
using namespace std;
double frac(int a,int b){return 1.0*a/b;}
double DP[1005][1005];
int w,b;
int main()
{
scanf("%d%d",&w,&b);
DP[0][0]=0; //都没抽到,B赢
for(int i=1;i<=w;i++) DP[i][0]=1; //全是白鼠,A赢
for(int j=1;j<=b;j++) DP[0][j]=0; //全是黑鼠,B赢
for(int i=1;i<=w;i++){
for(int j=1;j<=b;j++){
DP[i][j]+=1.0*i/(i+j); //先手直接抽到白鼠
if(i>=1&&j>=2) DP[i][j]+=DP[i-1][j-2]*frac(j,i+j)*frac(j-1,i+j-1)*frac(i,i+j-2); //A黑鼠,B黑鼠,跑白鼠
if(j>=3) DP[i][j]+=DP[i][j-3]*frac(j,i+j)*frac(j-1,i+j-1)*frac(j-2,i+j-2); //A黑鼠,B黑鼠,跑黑鼠
}
}
printf("%.9lf",DP[w][b]);
return 0;
}
B - P4316 绿豆蛙的归宿
拓扑+DP。
搞一个反图,跑拓扑的同时算期望:每个点的期望距离=(他所有前缀的期望距离+路径长度)*概率。
#include <bits/stdc++.h>
using namespace std;
struct Graph{
int Val[200005],Go[200005],Deg[100005],Deg2[100005];
int Head[100005],Next[200005],tot;
void Add_edge(int u,int v,int w){++tot,Next[tot]=Head[u],Head[u]=tot,Val[tot]=w,Go[tot]=v,Deg[v]++,Deg2[v]++;}
}G;
int node[100005],cnt;
double dis[100005];
int n,m,u,v,w;
queue<int>q;
void TUPO(int u){
for(int i=1;i<=n;i++) if(G.Deg[i]==0) q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
node[++cnt]=u;
for(int i=G.Head[u];i;i=G.Next[i]){
int v=G.Go[i];G.Deg[v]--;
dis[v]+=1.0*(dis[u]+G.Val[i])/G.Deg2[v];
if(G.Deg[v]==0){
q.push(v);
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
G.Add_edge(v,u,w);
}TUPO(n);
printf("%.2lf",dis[1]);
return 0;
}
C - CF768D Jon and Orbs
为什么感觉比 A,B 简单
设 \(dp_{i,j}\) 已经取了 \(i\) 次,取出了 \(j\) 种的概率,一共有 \(k\) 种,\(dp_{0,0}=1\)。
然后转移,有这几种情况:
- 某一天抓到了已经抓过的,\(dp_{i,j}=dp_{i-1,j}\times\frac{j}{k}\)
- 某一天抓到了没有抓过的,\(dp_{i,j}=dp_{i-1,j-1}\times\frac{k-j+1}{k}\)
我们的 \(i\) 最大期望其实就是调和级数 \(O(n \ln n)\) 级别的,开个 \(10000\) 左右差不多,复杂度也可以。
预处理就好了,不要每一个询问算一次。
#include <bits/stdc++.h>
using namespace std;
const int maxn=10000;
double DP[10005][1005];
int k,q,p[10005];
int main()
{
scanf("%d%d",&k,&q);
for(int i=1;i<=q;i++){
scanf("%d",&p[i]);
}
DP[0][0]=1;
for(int i=1;i<=maxn;i++){
for(int j=1;j<=k;j++){
DP[i][j]+=1.0*DP[i-1][j]*j/k;
DP[i][j]+=1.0*DP[i-1][j-1]*(k-j+1)/(k);
}
}
for(int i=1;i<=q;i++){
for(int j=1;j<=maxn;j++){
if(DP[j][k]>=p[i]/2000.0){
printf("%d\n",j);
break;
}
}
}
return 0;
}
D - P1365 WJMZBMR打osu! / Easy
不会。
E - P1850 [NOIP2016 提高组] 换教室
不会。
F - P2473 [SCOI2008] 奖励关
不会。
G - CF24D Broken robot
不会。
H - P3232 [HNOI2013] 游走
不会。
标签:frac,int,Day2,times,2024,黑鼠,DP,dp From: https://www.cnblogs.com/Sundar-2022/p/18076078