hdu 5036 Explosion||2014 北京区域赛网络赛 (概率+bitset优化的状态压缩+floyd传递闭包)

题目链接

题意:有n扇门,n种钥匙,一一对应。每扇门打开后可能得到k把钥匙(k可能为0)。一扇门还可以用一颗炸弹炸开。现在问要开所有门,使用炸弹的期望个数。

思路:状态压缩。用一个二进制串表示每扇门能打开的门的信息,对应的位上为1表示能打开,为0表示不能打开。

状态是可以传递的。。[……]

Read more

hdu 4336 Card Collector (2012多校 #4) (容斥原理模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=4336

题意:有n种卡片,买一包干脆面得到第i种卡片的概率是p[i],每包干脆面最多有一张卡片,问收集齐所有卡片要买的干脆面的包数的数学期望。

思路:容斥模板题。1.0/p[i]就是拿到某张卡片需要买的[……]

Read more

codeforces 148 D. Bag of mice

http://codeforces.com/problemset/problem/148/D
题意:盒子里有w只白老鼠,b只黑老鼠,公主和魔王轮流取(公主先),先取到白老鼠的人获胜。魔王每次取完以后,盒子中的老鼠会因为吓尿了跑掉一只,跑掉的老鼠不算任何人取的。问公主获胜的概率。

思路:概率dp.[……]

Read more

codeforces 107 B. Basketball Team

http://codeforces.com/problemset/problem/107/B

题意:有m个部门,每个部分s[i]个人,HW在第h部门,现在要从这m个部门中挑选包括HW在内的n个人去参加比赛,问被挑选的人中有HW的队友(同部门的人)的概率是多少。如果m个部分的人数不够组成n人的球队,[……]

Read more

codeforces 518 D. Ilya and Escalator

http://codeforces.com/problemset/problem/518/D

题意:有n个人排队上一个电梯。。。在某一秒内,队首的人有p的概率上电梯,1-p的概率不动。每个人只有在队首的位置才可以上电梯(也就是每一秒内,最多只有一个人可以上电梯)。电梯无线长(也就是上了电梯就不会离[……]

Read more

codeforces 312 B. Archer

http://codeforces.com/problemset/problem/312/B
题意:两个人比赛射箭,先射的人射中的概率是a/b,后射的人射中的概率是c/d,问先射的人赢的概率。
思路:应该叫条件概率。。。? 不过我们可以用古典概型的思维想。每射一次看成一个点,射中的点用白色表示,[……]

Read more

codeforces 476 B. Dreamoon and WiFi

http://codeforces.com/problemset/problem/476/B
题意:给出两个长度相等-且不超过10的字符串,串1只包含‘-’,’+‘。按照‘+’为1,‘-’为-1累加可以得到一个值。串2还包含若干‘?’,代表该处的值不确定,且为’+’和’-‘的概率相等,都是0.5.[……]

Read more

codeforces 30 C. Shooting Gallery

http://codeforces.com/contest/30/problem/C
题意:给出n个target在一个二维平面上。给出每个target的坐标,出现的时间,以及击中的概率。target出现之后就会瞬间消失,枪移动的单位速度为1,射击不需要时间。问能击中的target的最大期望是多少。[……]

Read more