codeforces 476 B. Dreamoon and WiFi

http://codeforces.com/problemset/problem/476/B
题意:给出两个长度相等-且不超过10的字符串,串1只包含‘-’,’+‘。按照‘+’为1,‘-’为-1累加可以得到一个值。串2还包含若干‘?’,代表该处的值不确定,且为’+’和’-‘的概率相等,都是0.5.问串2的值和串1相等的概率。
思路:我们可以扫一遍得到‘?’的个数和两个式子的差值。设问号个数为a,差值为b,那么在a个问号中需要有(a-b)/2个为‘+’(容易知道,a,b一定奇偶性相同,所以a-b一定能被2整除),根据超几何分布,概率为 c[a][(a-b)/2]*(1/2)^a; 写的时候可以先打个组合数的表。1A,开心。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz