Fizzmy

题解

--------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) 期望DP(4) 未归档(5) 树形dp(4) 模拟(1) 模板(3) 游记(1) 状态压缩(8) 线段树(12) 组合数学(1) 网络流(4) 脑洞(8) 莫比乌斯反演(2) 贡献法(3)

归档

标签

去牛客网

/ 注册

全部文章 / 题解（共2篇）

2021牛客多校第一场I Increasing Subsequence-期望DP

题意：一个长为的排列，有两个人轮流从中取数，每一轮中所取的数需要满足如下规则：取的数大于之前所有人取的数取的数的下标大于取数人之前取的数的下标如果有多种取数方案，则随机进行取数第一个人第一次取数随机如果有人没法再取数，游戏结束求最后期望能取数多少次。 Solution: 期望...

DP 期望DP

2021-08-18

2 482

牛客第7场I-Valuable Forests

题意：定义一个无根树的权值为所有点的度数的和，求有标号的n个点形成的所有森林的权值的和。 Solution: 比赛时脑抽，考完五分钟后过了... 由prufer序列的结论可得，对于n个点的无根树，可以形成个不同的树，我们记他的值为,那么对于n个点的森林的个数，我们可以求得DP式子：可以看成将...

prufer DP

2020-08-01

19 440