P2719 搞笑世界杯

· · 题解

Problem

Solution1

看到题目，很容易想到用 dp。

设 f(i,j) 表示已经售出 i 张 A，j 张 B 后两人买到票相同的概率

易得状态转移方程：f(i,j)=\dfrac{f(i-1,j)+f(i,j-1)}{2}

注意初始状态： \forall 1 \le i \le n , f(i,0)=f(0,i)=1 即全部都是一种票时拿到一样的票的概率是 100 \% 。

Code1

时间复杂度 \Theta(n^2) 。


/*dp*/

#include<bits/stdc++.h>
using namespace std; 
int n;
double f[1251][1251];
int main()
{
    cin>>n;
    n/=2; //因为题目给出的是2n
    for(int i=2;i<=n;i++)
       f[i][0]=1,f[0][i]=1; //初始化
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=f[i-1][j]/2+f[i][j-1]/2;  //动态规划
    printf("%.4lf",f[n][n]);
    return 0;
}

Solution2

这题其实还有排列组合的方法。

最后两张不同的概率 P 可以用前 2n-2 张中有 n-1 张 A 和 n-1 张 B 。

P = C^{n-1}_{2n-2} \cdot (\dfrac{1}{2})^{2n-2} = \dfrac{(2n-2)!}{4^{n-1}(n-1)!(n-1)!} = \dfrac{(2n-2) \times (2n-3) \times \dots \times n}{(4\times{(n-1)}) \times (4\times{(n-2)}) \times \dots \times (4\times{1})}

最终答案为 1-P 。

Code2

直接计算即可，时间复杂度 \Theta (n)。

/*排列组合*/

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;cin>>n;n>>=1;//因为题目给出的是2n
    double ans=1.0;//即上述的P
    for(int i=1;i<n;i++)
        ans=ans*(i+n-1)/(i<<2);//暴力计算
    printf("%.4lf",1-ans);
    return 0;
}