首页 > 其他分享 >谢老师2024春 - Day2:期望DP

谢老师2024春 - Day2:期望DP

时间:2024-03-15 19:11:08浏览次数:21  
标签:frac int Day2 times 2024 黑鼠 DP dp

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

相关文章

  • 从 VNCTF2024 的一道题学习QEMU Escape
    说在前面本文的草稿是边打边学边写出来的,文章思路会与一个“刚打完用户态pwn题就去打QEMUEscape”的人的思路相似,在分析结束以后我又在部分比较模糊的地方加入了一些补充,因此阅读起来可能会相对轻松。(当然也不排除这是我自以为是)题目github仓库[1]题目分析流程[1-1]......
  • 2024-03-15
    2024-03-15美好的一天昨天剩下的题一个字符串重新标号之后可以形成回文串当且仅当每个字母在这个串中出现的次数要么全是偶数要么只有一个奇数我们只关心出现次数的奇偶性,可以用异或来记录用一个长度为26的01串st来记录,第i位表示('a'+i)这个字母出现次数的奇偶......
  • 20240315打卡
    第三周第一天第二天第三天第四天第五天第六天第七天所花时间3h5h0h1h0h代码量(行)2742560640博客量(篇)11111知识点了解完成AndroidStudio中原生数据库SQlite简单的CRUD本地数据库连接到远程数据库海底谭练习python的Pyautogui,自动......
  • 2024-03-14 leetcode写题记录
    目录2024-03-14leetcode写题记录829.连续整数求和题目链接题意解法2024-03-14leetcode写题记录829.连续整数求和题目链接829.连续整数求和题意给定一个正整数\(n\),返回连续正整数满足所有数字之和为\(n\)的组数。示例1:输入:n=5输出:2解释:5=2+3,共有两......
  • 2024前端 JS面试题
    目录1,JS数据类型2,JS两种数据类型1,基本数据类型1,基本数据类型的值不可变2,基本数据类型不可以添加属性和方法:3,基本数据类型的赋值是简单的赋值4,基本数据类型的比较是值的比较:5,基本数据类型的值存放在栈内存中6,基本数据类型详解1,undefined2,Null3,string4,Number5,Bo......
  • 树形DP 01
    树形DP1、没有上司的舞会(选或不选)题目描述某大学有\(n\)个职员,编号为\(1\ldotsn\)。他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数\(r_i\),但是呢,如果某个职......
  • 10大超好用ai软件,2024办公学习必备!
    人工智能(AI)近年来取得了显着进步,并已成为科技行业的流行语。我们随时能看到大量个关人工智能工具的资讯,它有可能自动执行任务,节省时间并提高效率,使其成为企业的宝贵资产和平台。随着人工智能的进步,旨在让企业生活更轻松的人工智能软件不断涌现,这些人工智能软件旨在自动......
  • 大家觉得2024了,还有必要搭建自己的博客吗?
    其实,这个问题我之前也纠结了很久了,现在各种自媒体平台都适合记录生活,但是,这些都是公开的,就感觉在裸奔一样,没有安全感和隐私感,而个人博客就可以规避这一点,比如可以做一个个人用的知识库,资料库,家庭照片等,只要自己记住网址,不公开,那么相当是比较安全的。你觉得呢,欢迎在评论区说下你......
  • 2024最新整理Python入门教程(超详细),从零基础入门到精通,看完这一篇就够了
    前言本文罗列了Python零基础入门到精通的详细教程,内容均以知识目录的形式展开。01.python由来与发展介绍02.项目开发流程【文末有惊喜福利......
  • 2024年江西省各市区县高新技术企业申报奖励补贴标准金额及政策解读
    一、江西省高新技术企业优惠扶持政策1、对已获得省外高新技术企业证书的企业在我省设立生产高新技术产品的二级分支机构,可申请减按15%优惠税率缴纳企业所得税;对已获得省外高新技术企业证书的企业在我省投资设立的生产同一高新技术产品的全资子公司,视同我省认定的高新技术企业,备......