生之、如舟

分类

动态规划(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人学习

全部文章（共166篇）

HDU6486 Flower 【思维】来自专栏

http://acm.hdu.edu.cn/showproblem.php?pid=6486要让所有数都俩俩差值为0，让N-1一个数-1，对于差值的影响，就是没有-1的那个数进行+1，最大操作次数为mx-1，现在要让每个数与最大值的差值为0，那么需要的操作次数就是sum(mx - a[i]),然后s...

思维题

2021-01-14

0 637

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

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 710

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

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

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

概率

2021-01-12

0 643

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