http://codeforces.com/contest/625/problem/C 题意：构造一个矩阵。。满足三个条件。。。 思路：简单构造。。。看代码把。。。。 /* *********************************************** Author :111qqz Created Time :2016年02月07日 星期日 17时49分15秒 File Name :code/cf/#342/C.cpp ************************************************ */ #include <cstdio> #include <cstring> …

http://codeforces.com/contest/625/problem/B 题意：给出两个字符串，问要替换掉多少个字符才能使得前者中不包含后者。 思路：直接搞...找到一个把收尾替换成‘#’,然后下次从该位置继续开始找，直到找不到。 /* *********************************************** Author :111qqz Created Time :2016年02月07日 星期日 17时31分33秒 File Name :code/cf/#342/B.cpp ************************************************ */ #include …

http://codeforces.com/contest/625/problem/A 题意：有n块钱，塑料瓶饮料a元一瓶，玻璃瓶饮料b元一瓶，退还玻璃瓶可以得到c元。问最多能买多少瓶饮料。 思路：贪心。如果塑料瓶比玻璃瓶的实际价格便宜，那么一定买塑料瓶的，否则先买玻璃瓶，再用塑料瓶填。注意一些边界的判断。。 /* *********************************************** Author :111qqz Created Time :2016年02月07日 星期日 17时02分32秒 File Name :code/cf/#342/A.cpp …

http://codeforces.com/problemset/problem/148/D 题意：盒子里有w只白老鼠，b只黑老鼠，公主和魔王轮流取（公主先），先取到白老鼠的人获胜。魔王每次取完以后，盒子中的老鼠会因为吓尿了跑掉一只，跑掉的老鼠不算任何人取的。问公主获胜的概率。 思路：概率dp.. dp[i][j]表示有i只白老鼠，j只黑老鼠的时候公主获胜的概率。 转移方程 1. 公主抽到白老鼠（之后龙不必再抽） 胜率为i/(i+j)*1 2. 公主抽到黑老鼠，龙抽到黑老鼠，跳出一只黑老鼠，胜率为j/(i+j) * (j-1)/(i+j-1) * (j-2)/(i+j-2) * f[i][j-3] (j>=3) 3. …

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是 …

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], …

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

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）， /* *********************************************** Author :111qqz …

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

http://codeforces.com/contest/621/problem/A A. Wet Shark and Odd and Even time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Today, Wet Shark is given n integers. Using any of these integers no more than once, Wet Shark wants to get maximum possible even …