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

题目链接

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

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

状态是可以传递的。。

如果第i扇门能打开门k,那么能打开第i扇门的第j扇门也可以打开门k。

状态压缩以及传递的过程可以很容易用bitset来维护,这才是bitset的正确打开姿势

相当于用floyd做了一个传递闭包。(floyd的有一层循环隐藏在了bitset中,复杂度没有改变,但是常数小)

最后对于期望的计算方法:统计能打开第i扇门的方案数计为cnt,这cnt的方案中,只有一种是用炸弹炸掉,因此用的炸弹数的期望数为1/cnt

由于期望的独立性,因此打开所有门所有的炸弹数的期望就是每个门的期望累加。

 

 

 

 

 

 

 

 

hdu 5645 DZY Loves Balls (古典概型)

题目链接
题意:n(n<=300)个球,每个球上标有一个标号(a[i]<=300),从中拿一个,不放回,再拿一个,问第一个球上的数字严格大于第二个球上的数字的概率。 思路:古典概型。总数为n*(n-1)/2...然后标号最大300,不妨用cnt[i]统计标号为i的球的个数。从小往大扫一遍cnt,cnt[i]对分子的贡献就是cnt[i]*cur。。cur 为 sum{cnt[1]..cnt[i-1]}; 最后注意将分子除以2,因为有一半是第一个球比第二个球小的情况。

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

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

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

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

注意体会这种具体应用容斥的模拟方法,把1<<n转化成二进制来模拟有1个元素的集合,有2个元素的集合…有n个元素的集合。
核心代码:

 

20160305update:前几天有道题没写递归形式tle掉了。。。所以来学习一下容斥原理的递归形式。

以及这道题用递归的形式写了一遍。

codeforces 148 D. Bag of mice

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

思路:概率dp.. dp[i][j]表示有i只白老鼠,j只黑老鼠的时候公主获胜的概率。

转移方程

 

codeforces 107 B. Basketball Team

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

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

思路:考虑一般情况。至少有一个队友的情况较多,应该从反面考虑,即没有一个队友的情况。选完HW以后面临的状态是:事件总数为从total(m个部门的人员之和)-1个人中选n-1个的方案数,包含的事件数目为从a(a=total-s[h])中选n-1个人包含的方案数。 可以看出分母相同,可以约掉。

然后对于边界情况,首先判断total是否比n小。然后,如果a<n-1,表示除去HW所在的h部分之外的人不可能组成n-1个人,也就是一定要选择HW的队友,概率为1.

 

 

 

codeforces 518 D. Ilya and Escalator

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

题意:有n个人排队上一个电梯。。。在某一秒内,队首的人有p的概率上电梯,1-p的概率不动。每个人只有在队首的位置才可以上电梯(也就是每一秒内,最多只有一个人可以上电梯)。电梯无线长(也就是上了电梯就不会离开了),问在第t秒的时候,电梯上的人的个数的数学期望是多少。

思路:一开始推公式的我还是图样。这题是dp.其实也不难想。dp[i][j]表示第i秒时电梯上有j个人的概率。 当j==n的时候,也就是所以人都上了电梯以后。dp[i+1][j]+=dp[i][j],对于其他时刻 dp[i+1][j+1]+=dp[i][j]*p,dp[i+1][j]+=dp[i][j]*(1-p).  初始化dp[0][0]=1,即0时刻电梯上有0个人的概率为1.

 

 

codeforces 312 B. Archer

http://codeforces.com/problemset/problem/312/B
题意:两个人比赛射箭,先射的人射中的概率是a/b,后射的人射中的概率是c/d,问先射的人赢的概率。
思路:应该叫条件概率。。。? 不过我们可以用古典概型的思维想。每射一次看成一个点,射中的点用白色表示,没有射中的用黑色表示。如果两个人第i次都没有射中,那么就要继续第i+1 轮,而第i+1轮和之前的每一轮是独立的。等于重复这个过程。所以古典概型的样本总量应该减去宝石两个人都没有射中的点的个数,为b*d-(b-a)*(d-c),整理为b*c+a*d-a*c,设为n.要想第一个人赢,那么对于某一次,只要不是第一个人没射中,第二个人射中这种情况,就都是第一个人赢。而第一个人没射中的事件数为b-a,第二个人射中的事件数为c,总数为(b-a)*c,所以答案为(n-(b-a)*c)/n

 

codeforces 453 A. Little Pony and Expected Maximum

http://codeforces.com/problemset/problem/453/A
题意:m面筛子,每面点数出现的概率相同,连续投掷n次,问出现的最大值的数学期望。
思路:手写样例。。。发现答案为 。。。记得把(1/m)^n放进去。

观察答案,可以这样理解(我是用样例推出公式后理解。。。数学差的人心好累):如果i为最大值,那么n次每次必须投掷出1..i的点数,概率为 (i/m)^n,但是要至少有一个投掷成i,也就是要减去所有的数都是1..i-1中的情况(概率 为((i-1)/m)^n),

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,开心。

 

 

codeforces #341 div2 C. Wet Shark and Flowers

http://codeforces.com/contest/621/problem/C

C. Wet Shark and Flowers
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There are n sharks who grow flowers for Wet Shark. They are all sitting around the table, such that sharks i and i + 1 are neighbours for all i from 1 to n - 1. Sharks n and 1 are neighbours too.

Each shark will grow some number of flowers si. For i-th shark value si is random integer equiprobably chosen in range from lito ri. Wet Shark has it’s favourite prime number p, and he really likes it! If for any pair of neighbouring sharks i and j the product si·sj is divisible by p, then Wet Shark becomes happy and gives 1000 dollars to each of these sharks.

At the end of the day sharks sum all the money Wet Shark granted to them. Find the expectation of this value.

Input

The first line of the input contains two space-separated integers n and p (3 ≤ n ≤ 100 000, 2 ≤ p ≤ 109) — the number of sharks and Wet Shark’s favourite prime number. It is guaranteed that p is prime.

The i-th of the following n lines contains information about i-th shark — two space-separated integers li and ri(1 ≤ li ≤ ri ≤ 109), the range of flowers shark i can produce. Remember that si is chosen equiprobably among all integers fromli to ri, inclusive.

Output

Print a single real number — the expected number of dollars that the sharks receive in total. You answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let’s assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

Sample test(s)
input

output

input

output

Note

A prime number is a positive integer number that is divisible only by 1 and itself. 1 is not considered to be prime.

Consider the first sample. First shark grows some number of flowers from 1 to 2, second sharks grows from 420 to 421flowers and third from 420420 to 420421. There are eight cases for the quantities of flowers (s0, s1, s2) each shark grows:

  1. (1, 420, 420420): note that s0·s1 = 420, s1·s2 = 176576400, and s2·s0 = 420420. For each pair, 1000 dollars will be awarded to each shark. Therefore, each shark will be awarded 2000 dollars, for a total of 6000 dollars.
  2. (1, 420, 420421): now, the product s2·s0 is not divisible by 2. Therefore, sharks s0 and s2 will receive 1000 dollars, while shark s1 will receive 2000. The total is 4000.
  3. (1, 421, 420420): total is 4000
  4. (1, 421, 420421): total is 0.
  5. (2, 420, 420420): total is 6000.
  6. (2, 420, 420421): total is 6000.
  7. (2, 421, 420420): total is 6000.
  8. (2, 421, 420421): total is 4000.

The expected value is .

In the second sample, no combination of quantities will garner the sharks any money.

 

 

 

题意:有n个区间,第i个和第i+1个相邻,特别地,第n个和第1个也是相邻的。 每个区间选择每个数的可能性是相同的。如果一个组相邻区间选到的两个数的乘积可以被给定的素数p整除,那么这两个区间各得2000分,问所有区间的得分的期望总和是多少。

 

思路: 如果乘积是能被p整除,那么这两个数中至少有一个能被p整除。

而这两个数具体是多少我是不关心的。。我们只关心它能不能被p整除。

由加法原理,期望总和等于所有组相邻的区间的期望之和。

对于任意一组相邻区间,两个数的乘积能整除p有三种情况。。。比较复杂。。不妨考虑反面。即两个数都不能被p整除。 

如果我们能够统计出每个区间内能被p整除的数的个数,这个概率就可以求出来了。

而对于任意一个区间,[l,r],直接统计能被p整除似乎有些困难,需要分情况讨论。

我们不妨从初始划分。将区间[l,r]分成[1,l-1]和[1,r]  1到x中能被p整除的数的个数为x/p.

所以区间[l,r]中能被p整除的个数为 r/p-(l-1)/p;(考虑这种方法的一般意义,即如果要统计某个区间的某种数量,正面直接难统计的话,我们可以间接来统计,可能是从1,也可能是从0)

需要注意的是:对于输出绝对误差/相对误差不超过1E-x的输出要求。。。保留的小数位至少要x+2位才比较保险。。。。。

 

 

codeforces 30 C. Shooting Gallery

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

思路:路径dp。。。按照时间升序排列。 dp[i]表示到第i个target出现的时候的期望。

hdu 5481||bestcoder #57 div 2 C Desiderium (概率)

Desiderium

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 427    Accepted Submission(s): 167

Problem Description

There is a set of intervals, the size of this set is n.

If we select a subset of this set with equal probability, how many the expected length of intervals’ union of this subset is?

We assume that the length of empty set’s union is 0, and we want the answer multiply 2n modulo 109+7.

 

Input

The first line of the input is a integer T, meaning that there are T test cases.

Every test cases begin with a integer n ,which is size of set.

Then n lines follow, each contain two integers l,r describing a interval of [l,r].

1n100,000.

1,000,000,000lr1,000,000,000.

 

Output
For every test case output the answer multiply 2n modulo 109+7.

 

Sample Input
2
1
0 1
2
0 2
1 3

 

Sample Output

1 7

Hint

For the second sample, the excepted length is $frac{0+2+2+3}{4}=frac{7}{4}$.

比赛的时候并没有做出来…sad..
因为b题调了太久…这题基本就没时间了...果然还是太弱了QAQ
然后发现有时间也做不出…
题意真是好难懂...
转载一段题解:

一个含有n个区间的集合,从该集合中等概率地选取子集,求所有子集中的所有区间的构成的并集长度的和。

第二个样例解释:

集合中含有2个区间:一个是[0,2],编号为1,一个是[1,3],编号为2。

集合的子集有4个:

1、空集,集合中区间的并的长度为0

2、{区间1},集合中区间的并的长度为2

3、{区间2},集合中区间的并的长度为2

4、{区间1、区间2},集合中区间的并为[0,3],长度为3

考虑某一个区间对于答案的贡献:

若某个区间没有被其它区间覆盖,则该区间在子集中出现的总次数为:2^(n-1)次(总子集数-去掉该区间的子集总数)

若某个区间被覆盖了1次,即有2个区间重叠,那么该区间在子集中出现总次数为:2^(n-1)+2^(n-2)次(第1个区间在子集中出现的次数+第2个区间在子集中出现且第1个区间不出现的总次数)

…………

可以得到

若该区间被覆盖了k(k>=0)次,即有k+1个区间重叠,得到该区间在所有子集中出现的总次数:2^(n-1)+2^(n-2)+……+2^(n-k-1)

如何统计每一个区间的重叠次数?

对于输入的每一个区间的两个端点,给一个权值,左端点为1,右端点为-1。然后把所有端点按照位置从小到大排序。从左往右扫一遍,累加端点的权值,得到的当前的权值和就是当前所在区间的重叠次数。

累加每个区间的重叠次数*区间长度,即为所求。

cf 442B Andrey and Problem

B. Andrey and Problem
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Andrey needs one more problem to conduct a programming contest. He has n friends who are always willing to help. He can ask some of them to come up with a contest problem. Andrey knows one value for each of his fiends — the probability that this friend will come up with a problem if Andrey asks him.

Help Andrey choose people to ask. As he needs only one problem, Andrey is going to be really upset if no one comes up with a problem or if he gets more than one problem from his friends. You need to choose such a set of people that maximizes the chances of Andrey not getting upset.

Input

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of Andrey’s friends. The second line contains n real numbers pi(0.0 ≤ pi ≤ 1.0) — the probability that the i-th friend can come up with a problem. The probabilities are given with at most 6 digits after decimal point.

Output

Print a single real number — the probability that Andrey won’t get upset at the optimal choice of friends. The answer will be considered valid if it differs from the correct one by at most 10 - 9.

Sample test(s)
input

output

input

output

Note

In the first sample the best strategy for Andrey is to ask only one of his friends, the most reliable one.

In the second sample the best strategy for Andrey is to ask all of his friends to come up with a problem. Then the probability that he will get exactly one problem is 0.1·0.8 + 0.9·0.2 = 0.26.

 

可以选1个,可以选2个,选i个….

但是选哪i个,似乎还要枚举…这样计算起来很麻烦

但是再一看,很容易发现,选i个概率最大的情况一定是选本身概率最大的i个的情况

那么我们只需要枚举选的个数,取每种情况的最大值就好了.