题解：CF1599C Bubble Strike

思路

分类讨论。设学过的地图个数为

x

，则选到自己学过的地图的情况分为以下几类（为了方便表述，将“学过的地图”称为 A 地图，反之称为 B 地图）：

随机抽到了 $3$ 张 A 地图，概率为 $\dfrac{\dbinom{x}{3}}{\dbinom{n}{3}}$ ；
随机抽到了 $2$ 张 A 地图，此时我们可以扔去那一张 B 地图，必定可以，概率为 $\dfrac{\dbinom{x}{2}\dbinom{n-x}{1}}{\dbinom{n}{3}}$ ；
随机抽到了 $1$ 张 A 地图，概率为 $\dfrac{\dbinom{x}{1}\dbinom{n-x}{2}}{\dbinom{n}{3}}\times\dfrac{1}{2}$ 。

对 3. 中

\dfrac{1}{2}

含义的解释如下：

首先自己会选择扔去

2

张 B 地图之一，称为 X，剩下的那一张 B 地图称为 Y。我们可以将对手的选择看成是随机的，则他有

\dfrac 1 3

的概率选中 X 扔去，然后系统有

\dfrac12

的概率选中 A 地图；有

\dfrac 1 3

的概率选中 Y 扔去，此时必定可以；有

\dfrac 1 3

的概率选中 A 地图扔去，此时必定不可以。故对于某一种符合 3. 条件的地图随机抽取，选中 A 地图的概率为

\dfrac13\times\dfrac12+\dfrac13=\dfrac12

。

由于

n

的范围很小，故可以枚举

x

逐一检验。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long double LD;
int C3(int x){return x*(x-1)*(x-2)/6;}
int C2(int x){return x*(x-1)/2;}
int main(){
	int n;LD p;
	cin>>n>>p;
	for(int x=0;x<=n;x++)
		if(LD(C3(x)+C2(x)*(n-x)+LD(x*C2(n-x))/2)/C3(n)>=p)
			cout<<x,exit(0);
	
	return 0;
}

题解：CF1599C Bubble Strike

文章操作

思路

Code

相关推荐

评论

题解：CF1599C Bubble Strike