hdu 5194 DZY Loves Balls 题解【组合数学】【概率期望】【打表/找规律】【枚举】
点击量:252
这个题的做法实在是太多了,在我打完暴力水过后发现这个题的很多解法都是非常有价值的。
Description
There are \(n\) black balls and \(m\) white balls in the big box.
Now, DZY starts to randomly pick out the balls one by one. It forms a sequence \(S\) . If at the \(i\)-th operation, DZY takes out the black ball, \(S_i=1\) , otherwise \(S_i=0\) .
DZY wants to know the expected times that \(\tt ’01’\) occurs in \(S\)
Input
The input consists several test cases. \((TestCase\le 150)\)
The first line contains two integers,\(n,m(1\le n,m\le 12)\)
Output
For each case, output the corresponding result, the format is \(p/q\) (\(p\) and \(q\) are coprime)
Sample Input
1 1 2 3
Sample Output
1/2 6/5
Hint
Case 1: \(S=\tt 01\) or \(S=\tt 10\), so the expected times \(=1/2=1/2\)
Case 2: \(S=\tt 00011\) or \(S=\tt 00101\) or \(S=\tt 00110\) or \(S=\tt 01001\) or \(S=\tt 01010\)
or \(S=\tt 01100\) or \(S=\tt 10001\) or \(\tt S=10010\) or \(\tt S=\tt 10100\) or \(S=\tt 11000\),
so the expected times \(= (1+2+1+2+2+1+1+1+1+0)/10=12/10=6/5\)Source
BestCoder Round #35
题意:
给出\(n\)个黑色小球和\(m\)个白色小球,随机排列,令白色为1,黑色为0。问期望出现多少个\(\tt 01\)。多组数据,化为最简分数输出。
题解:
这个题有很多做法,而且有的做法比较考察期望题和组合数学的能力,感觉还不错。
一、暴力预处理
我们可以预处理出每个数有多少个\(01\),再根据它有多少个\(0\),多少个\(1\)分类,最后按统计结果输出即可,时间复杂度\(O(2^{n+m}\cdot (n+m))\),但是可以过。
分母是\(01\)串的种类,即全排列;上下同除\(\gcd\)约分输出即可。
#include<cstdio>
#include<cstring>
long long cnt[25][25];//计数
short ppc[1<<24];
long long gcd(long long x,long long y)
{
if(!y)
return x;
return gcd(y,x%y);
}
long long frac[25][25];//i!/j!的结果
int main()
{
for(int i=0;i<=12;++i)
frac[i][i]=1;
for(int i=1;i<=24;++i)
for(int j=1;j<=i;++j)
if(i!=j)
frac[i][j]=frac[i-1][j]*i;
for(register int i=1;i<(1<<24);++i)
{
ppc[i]=ppc[i>>1]+(i&1);
if(ppc[i]>12)
continue;
int ans=0,d=1;
int t=i>>1,tmp=i&1;
while(t)
{
if(tmp==1)
ans+=(t&1^1);
tmp=t&1;
t>>=1;
++d;
}
cnt[d][ppc[i]]+=ans;
for(register int j=d+1;j<=24;++j)
cnt[j][ppc[i]]+=ans+tmp;
}
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
long long up=cnt[n+m][n]*frac[m][1];
long long down=frac[n+m][n];
long long g=gcd(up,down);
up/=g;
down/=g;
printf("%lld/%lld\n",up,down);
}
return 0;
}
二、组合数大力推导
我们可以先确定一个串中有几个\(01\),然后枚举它;接着枚举剩下的\(0\)或\(1\)分别在哪里。
对于确定的\(n\)和\(m\),枚举\(i\in[1,\min(n,m)]\)表示有多少个\(01\),假设我们选定\(i\)个\(0\),在它们后面加上\(1\),而且\(1\)只能在这些\(0\)后面或者整个序列的开头出现,那么我们用插板法把所有\(1\)分成\(i+1\)组,且序列的开头那一组可以没有元素,方案数为\(C_m^i C_n^i\)(分别为选\(i\)个\(0\)的方案和分组的方案),然后乘上它的贡献\(i\)即可。
分母上同样是\(01\)串种类\(C_{n+m}^n\)。
#include<cstdio>
int tri[25][25];//杨辉三角
int gcd(int x,int y)
{
if(!y)
return x;
return gcd(y,x%y);
}
int main()
{
tri[0][0]=1;
for(int i=1;i<=24;++i)
{
tri[i][0]=1;
for(int j=1;j<=i;++j)
tri[i][j]=tri[i-1][j-1]+tri[i-1][j];
}
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int mn=n<m?n:m;//n个1 m个0
int up=0,down=tri[n+m][n];
for(int i=1;i<=mn;++i)
up+=tri[m][i]*tri[n][i]*i;
int g=gcd(up,down);
up/=g;
down/=g;
printf("%d/%d\n",up,down);
}
return 0;
}
三、利用概率推答案找规律
因为我们要求的是期望,期望具有可加性,所以我们可以把每两个位置出现\(01\)的概率加起来,就是答案了。
对于每个\(i\in [1,n+m)\),我们可以计算它出现\(01\)的概率。在第\(i\)位出现\(0\)的概率是\(\frac{m}{n+m}\),同时在第\(i+1\)位出现\(1\)的概率是\(\frac{n}{n+m-1}\)(因为同时所以是条件概率)。然后有\(n+m-1\)个\(i\)的位置,因此答案是上述三者相乘,即\(\frac{nm}{n+m}\)。
#include<cstdio>
#include<cstring>
long long gcd(long long x,long long y)
{
if(!y)
return x;
return gcd(y,x%y);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int up=n*m;
int down=n+m;
int g=gcd(up,down);
up/=g;
down/=g;
printf("%d/%d\n",up,down);
}
return 0;
}
四、其他
网上有一些博客写了DP做法,但是我太弱感觉想着想着就想到递推了,所以就不展开讨论了。而且还有打类似的记搜的,这个题因为数据范围小(吧?),做法还是挺多的。最重要的是明白第三点推答案找规律的核心。
说点什么