生之、如舟

分类

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

/ 注册

TA的专栏 67篇文章 1人订阅

Ryuichi的算法分享

67篇文章 1416人学习

全部文章（共9篇）

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 739

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 884

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 730

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 865

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

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

数学期望

2021-01-12

0 728

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 819

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

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

数学期望

2021-01-12

0 625

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

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

数学期望

2021-01-11

0 671

Acwing216. Rainbow的信号【期望+位运算】来自专栏

网上好多异或都用的奇期间，偶区间来处理的。我是用的计数异或前缀和为0和为1的个数来处理的，比较好理解。但是要注意到前缀可以为空，多一个什么也不选，异或为0的前缀 #include <stdio.h> #include <cstring> #include <algori...

数学期望

2021-01-11

0 637