http://codeforces.com/problemset/problem/621/E 题意：有b组数，每组数均有n个且相同。你必须在每组选一个数，组成一个新数sum，使得sum % x == k，问方案数 % (1e9+7)。 思路：数位dp.首先考虑b不是很大的一般情况。dp[i][j]表示处理到前i个块的时候结果为j的方案数。那么转移方程就是：**dp[i][(j_10+t)%x] = dp[i-1][j]_cnt[t] ** cnt[i]表示数字i出现的个数。 但是由于b很大（1E9）,所以需要用矩阵加速。 /* *********************************************** …

http://codeforces.com/contest/621/problem/D 题意：给出12个式子，问哪个最大。 思路：主要记住两个。一个是比较指数形式的数一个常用办法是取对数，同时要考虑是否能取对数，分情况讨论对于不能取对数的情况经过变换去取对数。第二个是取了两次对数后比较时候的最大值可能是小于0的。所以初始时置于0不够小。官方题解说得很清楚。 The tricky Rat Kwesh has finally made an appearance; it is time to prepare for some tricks. But truly, we didn't expect it to be so hard for …

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 …