生之、如舟

数学

动态规划(8) 博弈论(1) 图论(7) 基本算法(29) 并查集(17) 思维(3) 数据结构(5) 数论(18) 最短路(4) 枚举(1) 树状数组(13) 树论(4) 模板(7) 比赛(15) 算法总结(3) 线段树(11) 蓝桥杯(1) 贪心(1)

/ 注册

全部文章 / 数学（共14篇）

P1297 [国家集训队]单选错位【期望】来自专栏

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-...

数学期望

2021-01-13

0 581

P4550 收集邮票赠券收集问题升级版【期望，推公式】来自专栏

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[...

数学期望

2021-01-13

0 707

SP1026 FAVDICE - Favorite Dice 赠券收集问题【期望，推公式】来自专栏

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...

数学期望

2021-01-13

0 572

Acwing 623. 投票【概率dp】来自专栏

dp[i][j] ：表示A被投了i票，B被投了j票，并以这个状态开始往后一直是i>j的概率看数据范围N和M都是2000，那么就可以把所有范围的i和j表示出来 #include <stdio.h> #include <cstring> #include <algo...

概率

2021-01-13

0 564

Codeforces Round #688 (Div. 2) D. Checkpoints 【期望 + 构造】来自专栏

直接贴网上的题解把。这样构造期望是指数型增长的，所以很大的数很快就构造好了。然后由于自己太弱，第一次看到期望可以通过移项来算，简单的变通都不会，服了啊E[i] = E[i-1] + 1 + 1/2 * E[i] + 1/2 * 0E[i-1] + 1:表示从E[i-1]转移到E[i]基础步数为1...

数学期望

2021-01-13

0 662

P1850 [NOIP2016 提高组] 换教室【期望dp】来自专栏

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

数学期望

2021-01-12

0 588

Acwing 232. 守卫者的挑战【概率】来自专栏

#include <stdio.h> #include <cstring> #include <algorithm> #include <vector> #include <stack> #include <queue> #in...

概率

2021-01-12

0 529

Acwing218. 扑克牌【期望】来自专栏

假如现在的牌有n张，已经用去了a，b,c,d张，还没拿到大小王当前到目标状态要拿取牌数的期望为：6中情况的期望相加：拿到a的概率就是(13-a)/n * 期望1拿到b的概率就是(13-b)/n * 期望2拿到c的概率就是(13-c)/n * 期望4拿到d的概率就是(13-d)/n * 期望4拿到小王...

数学期望

2021-01-12

0 647

P6154 游走[dag + dp + 数学期望] 来自专栏

#include <stdio.h> #include <cstring> #include <algorithm> #include <vector> #include <stack> #include <queue> #in...

数学期望

2021-01-12

0 502

Acwing217. 绿豆蛙的归宿【DAG+数学期望】来自专栏

需要使用记忆话，一个点的期望只去计算一次。 #include <stdio.h> #include <cstring> #include <algorithm> #include <vector> #include <stack> #inc...

数学期望

2021-01-11

0 535