Fizzmy

期望DP

--------DP--------(1) CDQ分治(1) DP(11) FFT(4) z-box(6) 主席树(1) 二分(2) 分数规划(1) 分治(1) 区间DP(3) 博弈论(2) 后缀数组(2) 哈希(1) 学习笔记(2) 容斥(1) 并查集(4) 强连通分量(1) 扫描线(1) 数位DP(3) 数论(12) 斯特林数(1) 暴力(2) 最小生成树(1) 最短路(1) 未归档(5) 树形dp(4) 模拟(1) 模板(3) 游记(1) 状态压缩(8) 线段树(12) 组合数学(1) 网络流(4) 脑洞(8) 莫比乌斯反演(2) 贡献法(3) 题解(2)

/ 注册

全部文章 / 期望DP （共4篇）

Codeforces908D New Year andArbitrary Arrangement-dp

传送门题意：给出 k,p1,p2 k , p 1 , p 2 ，一开始串为空，每次有 p1p1+p2 p 1 p 1 + p 2 的概率在串中加一个a， p2p1+p2 p 2 p 1 + p 2 的概率在串中加一个b，当串中有k个为ab的子序列停止加字符，求停止加字符后串中为ab...

2021-08-18

0 353

BZOJ4872: [Shoi2017]分手是祝愿-期望dp

传送门题意： B 君在玩一个游戏，这个游戏由 n 个灯和 n 个开关组成，给定这 n 个灯的初始状态，下标为从 1 到 n 的正整数。每个灯有两个状态亮和灭，我们用 1 来表示这个灯是亮的，用 0 表示这个灯是灭的，游戏的目标是使所有灯都灭掉。但是当操作第 i 个开关时，所有编号为 i...

2021-08-18

0 314

BZOJ5340: [Ctsc2018]假面-期望DP

传送门题意：有 2 个技能： 1.锁定：对一名指定的敌方单位使用，以 p 的概率对该单位造成 1 点伤害。 2.结界：在一片区域施放结界，让该区域内的所有其他单位无法动弹。如果一个单位的生命值降至 0 或 0 以下，那么该单位就会死亡。现在有 n 个敌方单位（编号从 1 至 n...

2021-08-18

0 257

洛谷P3830 [SHOI2012]随机树-期望DP

传送门题意：一棵含有n个叶子节点的二叉树通过如下方式生成：每次等概率的随机选择一个叶子节点，将这个节点加上左右两个子节点求： 1.叶子节点平均深度的期望 2.树深度的期望 n≤100 n ≤ 100 Solution: 第一问很好处理：设 fx f x 表示有x个叶...

2021-08-18

0 500