题解：CF1599C Bubble Strike

· · 题解

题目链接

思路

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

  1. 随机抽到了 3 张 A 地图，概率为 \dfrac{\dbinom{x}{3}}{\dbinom{n}{3}}；
  2. 随机抽到了 2 张 A 地图，此时我们可以扔去那一张 B 地图，必定可以，概率为 \dfrac{\dbinom{x}{2}\dbinom{n-x}{1}}{\dbinom{n}{3}}；
  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

#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;
}