开始学习！

http://acm.hdu.edu.cn/showproblem.php?pid=6486要让所有数都俩俩差值为0，让N-1一个数-1，对于差值的影响，就是没有-1的那个数进行+1，最大操作次数为mx-1，现在要让每个数与最大值的差值为0，那么需要的操作次数就是sum(mx - a[i]),然后sum(mx - a[i]) <= mx-1,就表示可以，否则不可以 #include <stdio.h> #include <cstring> #include <algorithm> #include <vector> #include &lt...

https://www.luogu.com.cn/problem/P1297 考虑期望的线性性。E(x + y + z) = E(x) + E(y) + E(z)跟x，y，z独立性无关` E(i)：表示第i个题正确的期望，这里也就是概率 * 1，所以跟概率是相等的。E(i) = min(a[i-1),a[i])/(a[i-1] * a[i])(a[i-1] * a[i]): 表示所有的情况数min(a[i-1),a[i])：表示两个题答案一一对应的情况数 #include <stdio.h> #include <cstring> #include <algor...

https://www.luogu.com.cn/problem/P4550 计算次数的期望部分 E[i] : 表示当前已经取得了i，再之后还需要E[i]次才能获得所有转移方程E[i] = i/N * E[i] + (N-i)/N * E[i+1] + 1做出一种转移，就需要消耗一次，所以+1E[i] = E[i+1] + N/(N-i),E[N] = 0 计算花钱的期望部分 f[i]: 表示当前已经取得了i，在之后还需要f[i]钱才能获得所有转移方程：f[i] = i/N * (f[i] + E[i] + 1) + (N-i)/N * (f[i+1] + E[i+1] + 1)E[i] ...

https://www.luogu.com.cn/problem/SP1026 E[i] : 表示当前已经取得了i，再之后还需要E[i]次才能获得所有转移方程E[i] = i/N * E[i] + (N-i)/N * E[i+1] + 1做出一种转移，就需要消耗一次，所以+1E[i] = E[i+1] + N/(N-i),E[N] = 0;代码 #include <stdio.h> #include <cstring> #include <algorithm> #include <vector> #include <stack> ...

dp[i][j] ： 表示A被投了i票，B被投了j票，并以这个状态开始往后一直是i>j的概率看数据范围N和M都是2000，那么就可以把所有范围的i和j表示出来 #include <stdio.h> #include <cstring> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <iostream> #include <map> #define go(i, l, r) fo...

直接贴网上的题解把。 这样构造期望是指数型增长的，所以很大的数很快就构造好了。然后由于自己太弱，第一次看到期望可以通过移项来算，简单的变通都不会，服了啊E[i] = E[i-1] + 1 + 1/2 * E[i] + 1/2 * 0E[i-1] + 1:表示从E[i-1]转移到E[i]基础步数为1+1/2 * E[i]：表示有1/2失败概率他要重走一遍到自身，所以加上走到i的步数期望的1/2+1/2 * 0 ：表示当前有1/2成功概率，这中情况不需要再走额外步数 #include <stdio.h> #include <cstring> #include <al...

状态表示很重要！dp[i][j][0]: 上完i节使用了j次申请，本节课没有申请的走过路程的期望dp[i][j][1]: 上完i节使用了j次申请，本节课使用申请的走过路程的期望转移方程直接看代码，太多了 #include <stdio.h> #include <cstring> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <iostream> #include <map> #de...