[CF98E]Help Shrek and Donkey

题意：A和B两个卡牌大师玩游戏，A有$n$张牌，B有$m$张牌，桌上有$1$张牌，这$n+m+1$张牌互不相同且A和B都知道这些牌里有什么牌（但他们互相不知道对方有什么牌，两个人也都不知道桌上的那张牌是哪张），游戏轮流进行，A先手，每轮可以①询问对方有没有某张牌，如果对方有，就要把它丢弃，否则表明自己没有这张牌②猜测桌上的牌，猜对了就赢，猜错了就输，问$A$和$B$获胜的概率（假设两人都磕了药足够聪明）

很棒的题啊！奇妙思路++

首先肯定只有在最后才会去猜测桌上的牌，因为要一发定输赢

假设这轮是A，下一轮是B，那么A可以去询问B有没有某张牌，这个询问有两种性质，可以是

①真询问，也就是随机询问对方有没有$m+1$张牌中的某一张

②假询问，也就是随机询问对方有没有自己$n$张牌中的某张牌

为什么要有假询问？因为这样做可以勾引B去猜桌上的牌，如果B猜错了，A自然就赢了

下面对A的询问真假性和B的反应分类讨论，设先手有$n$张牌，后手有$m$张牌时先手获胜的概率是$f\left(n,m\right)$

①A做真询问

如果问到B有的牌，那么B就知道A是在做真询问，局面就变成B扔掉一张牌并先手；此时A获胜的概率是$\dfrac{m}{m+1}\left(1-f\left(m-1,n\right)\right)$

如果恰好问到桌上那张牌：如果B认为A在做真询问，那么B就赢了；如果B认为A在做假询问，那么B之后就会认为桌上的牌不是这张，A就知道桌上的牌是这张，那么A就赢了，此时A获胜的概率应加上$\dfrac{1}{m+1}$

②A做假询问

如果B认为A是在做真询问，那么他就会猜错，A稳赢，获胜概率为$1$

如果B认为A是在做假询问，那么A和B都知道A有这张牌，和扔掉没有区别，所以局面相当于A扔掉一张牌后B先手，此时A获胜的概率为$1-f\left(m,n-1\right)$

假设A有$p$的概率选择真询问，有$1-p$的概率选择假询问，因为B会让A获胜的概率尽可能小，所以A的总获胜概率为

$\min\left\{\dfrac{pm}{m+1}\left(1-f\left(m-1,n\right)\right)+1-p,p\left(\dfrac{1}{m+1}+\dfrac{m}{m+1}\left(1-f\left(m-1,n\right)\right)\right)+\left(1-p\right)\left(1-f\left(m,n-1\right)\right)\right\}$

A要找到一个$p$使上面这个式子最大，如果把$p$作为自变量这其实就是两个一次函数取$\min$，一个单调递增一个单调递减，所以直接取交点即可

最后发现这其实是个DP，因为转移时下标比较鬼畜所以写成递归的形式会比较好

真是妙啊！

#include<stdio.h>
double p[1010][1010];
double du(int x){return x;}
void f(int n,int m){
	if(p[n][m]>0)return;
	if(n==0){
		p[0][m]=1/du(m+1);
		return;
	}
	if(m==0){
		p[n][0]=1;
		return;
	}
	f(m-1,n);
	f(m,n-1);
	double pr=p[m][n-1]/(p[m][n-1]+1/du(m+1));
	p[n][m]=pr*m/du(m+1)*(1-p[m-1][n])+1.-pr;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	f(n,m);
	printf("%.9lf %.9lf",p[n][m],1.-p[n][m]);
}

巴特西

[CF98E]Help Shrek and Donkey

最新文章

热门文章