CF464D World of Darkraft - 2
Codeforces Luogu 分析 显然装备之间没有区别，我们只要计算一种装备的期望，然后乘上 $k$ 即可。 考虑倒推。设 $dp_{i,j}$ 表示剩余 $i$ 个怪物、装备等级为 $j$ 期望获得的金币数，转移有三种： 选到了其它装备：概率为 $\frac{k-1}{k}$，期望收益为 $dp_{i-1,j}$。 选到了等级为 $j+1$ 的当前装备：概率为 $\frac{1}{...
标签 动态规划 / DP 下的文章
- 首页
- 动态规划 / DP
洛谷2519 [HAOI2011]Problem A
Luogu 分析 每个人的话相当于 $[a_i+1,n-b_i]$ 中的人排名相同。 那么如果两个人的话不同且对应的区间无交，他们就可能都说了真话。 把相同的区间缩在一起，问题变成每个区间有一个权值，选出若干个无交的区间使得权值和最大。 这个可以直接 DP，把所有区间按右端点排序后，二分找到最后的左端点小于当前右端点的位置，然后转移即可。 注意把 $a_i+1>n-b_i$ 的人掉，这...
洛谷5326 [ZJOI2019]开关
Luogu LOJ 分析 设 $P=\sum_{i=1}^n p_i$。 设 $F(x)$ 为按到目标状态的指数型概率生成函数，$G(x)$ 为按回自己的指数型概率生成函数。 $F(x)$ 直接把每个开关乘在一起即可，$G(x)$ 相当于是 $s_i=0$ 时的 $F(x)$。那么有 直接计算即可。 代码 // ==================================== //...
AGC038E Gachapon
AtCoder Luogu 分析 我不喜欢容斥，我不喜欢组合意义，我不喜欢生成函数，我也没有精神 首先 Min-Max 容斥一手 转移直接枚举 $d$ 即可。为了方便我们把容斥系数压到 DP 里去，转移要乘上一个 $-1$。 算答案就把上面这个东西代回去就好了。 代码 // ==================================== // author: M_sea //...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway 这个操作长得很像 LCT 中的 access。 于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。 因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n...
AGC035D Add and Remove
AtCoder 分析 可以发现题目中的贡献只有加，按照鸡贼的话来说这是一个很罕见的性质。 倒着看整个过程，相当于每次往里面加一个数。 我们考虑每个数对答案的贡献。假设当前有若干个数，第 $i$ 个数的贡献是 $x_i$，那么我们在 $i,i+1$ 中加一个数，新加的数的贡献显然是 $x_i+x_{i+1}$。 这个 $i,i+1$ 对应原序列中的一段区间，因此可以 DP。设 $dp_{l,r...
CF582D Number of Binominal Coefficients
Codeforces Luogu 分析 首先有一个定理： ${a+b\choose a}$ 质因数分解后 $p$ 的幂次等于 $p$ 进制下 $a+b$ 的进位次数。 于是可以把 $A$ 转成 $p$ 进制，然后考虑数位 DP。设 $dp_{i,j,0/1,0/1}$ 表示前 $i$ 位，进位 $j$ 次，第 $i-1$ 位是否向第 $i$ 位进位，$a+b$ 是否顶着 $A$ 的上界的...
JOISC2019 简要题解
官网 AtCoder LOJ 試験 / Examination 三维偏序板子，CDQ 即可。 代码 ビーバーの会合 / Meetings 首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。 我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。 那么直接递归处理链...
洛谷6295 有标号 DAG 计数
Luogu 分析 设 $f_i$ 为 $i$ 个点的 DAG 数量。 一个想法是枚举入度为 $0$ 的点的数量，有 多项式求逆即可。 现在还要求弱连通，那么把 $F(x)$ 求个多项式 $\ln$ 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blo...
CF1349D Slime and Biscuits
Codeforces 分析 设 $E(x)$ 为游戏结束时所有饼干都在 $x$ 手中的期望次数，$E'(x)$ 为游戏结束当且仅当所有饼干都在 $x$ 手中时的期望次数，$P(x)$ 为游戏结束时所有饼干都在 $x$ 手中的概率，$C$ 为所有饼干都在某个人手中时全部到另一个人手中的期望次数，则有 又因为 $g_0=f_0-f_1=n-1$，所以我们可以递推求出所有 $g_i$，从而求出所...