codevs 1060

葛修筠
2023-12-01

题目大意:

  有2n张票,分别有A,B两类,求最后两个人拿到同种票的概率。n<=1250;


想想这题应该是组合啊。。但是到底是组合还是排列。。如果是组合, 概率为:1-两种票都取了n-1张的情况,但是这两种票都取了n-1张的情况怎么算,C(n,n-1)*c(n,n-1)/所有情况,而所有情况又怎么算,对于留下来的两张票只有两种情况,留下来的都是A,留下来的都是B,留下来的有A也有B,那么这么算。。概率总在50%浮动。。不知道哪里有问题,看起来又都是问题。


那么就有了递推的做法。。

思想很简单。假设F[i][j]表示前i个人选了A类票j张的情况,那么有:

(1) 当j=0时,即没有人选A类票,在前i-1个人的基础上,第i个人有两种选择,根据乘法原理,那么前i个人选A的概率 f[i][0]=f[i-1][0]*0.5;

(2) 当j=n时,即前i-1个人已经将A的n张票都买走,或前i-1个人买了此类票的n-1张,根据加法原理,前i个人选n的概率 f[i][n]=f[i-1][n]+f[i-1][n-1]*0.5------但是对于i<n的时候是不可能出现这种情况的呀,那么循环是不是需要在i=n时开始。。

(3) 当j!=0,j!=n时,f[i][j]=f[i-1][j-1]*0.5+f[i-1][j]*0.5-----类似。。LCS的思想有没有?

#include<cstdio>
#include<cstdlib>
using namespace std;

double f[3000][3000];

int main()
{
	int n;
	scanf("%d",&n);
	
	n=n/2;
	
	f[0][0]=1;
	
	for (int i=1;i<=2*n;i++) f[i][0]=f[i-1][0]*0.5;
	
	for (int i=1;i<=2*n;i++)
	  for (int j=1;j<=n;j++)
	  if (j==n) f[i][j]=f[i-1][j-1]*0.5+f[i-1][j];
	   else f[i][j]=(f[i-1][j]+f[i-1][j-1])*0.5;
    
    printf("%.4lf",f[2*n-2][n]*2);
}

被坑到了n没除以2。。。调了很久。。

 类似资料:

相关阅读

相关文章

相关问答