闲扯之前感觉很难，但是自己推一推发现其实还好。 题面CF438E The Child and Binary Tree Solution设 $F(x)$ 表示权值为 $x$ 的二叉树的个数。 设 $C(x)$ 表示是否能选择权值为 $x$ 的点。 考虑枚举根结点的权值和左右子树的权值。 F(x)=\ ...

闲扯期望用倒推，这算是一个结论吗。。？ 题面P2473 [SCOI2008]奖励关 Solution由于这是期望题，我们考虑倒推（雾。 设 $dp_{i,S}$ 表示当前在第 $i$ 步，还未选择时已选集合为 $S$ 时，期望还能得到的分数。 若能够选择第 $j$ 个物品，那么： dp_{i,S} ...

闲扯感觉洛谷上的难度评价有问题啊。。。 题面P3251 [JLOI2012]时间流逝 Solution先简化题意： 给定 $n$ 个数，若当前的和为 $0$ ，那么可能随机的从这 $n$ 这个数中选一个，否则只能选择不大于当前已有值的最小值的数。手中有数时，有 $p$ 的概率去掉一个最小的数，问期望 ...

闲扯 $min-max$ 容斥 $+$ 树上高斯消元 $+$ 子集和变换 大概是叫这个吧 题面P5643 [PKUWC2018]随机游走 Solution我们设 $E_i$ 表示到达点 $i$ 的期望时间。问题就是求： \max_{i\in S}(E_i)显然可以用 $min-max$ 容斥来解决 ...

闲扯树上高斯消元模板题。 题面Maze Solution设 $E(u)$ 表示在 $u$ 点时，还需走的边数，那么 $E(1)$ 即为所求。 若 $u$ 是叶节点，我们有： E(u)=k_u E(1)+(1-k_u-e_u)(E_{fa_u}+1)否则，我们有： E(u)=k_u E(1)+\s ...

容斥学习笔记容斥的两种基本形式： |\bigcup_{i=1}^n A_i|=\sum_{k=1}^n (-1)^{k+1}(\sum_{1\leq i_1$min-max$ 容斥： max\{S\}=\sum_{T\in S} (-1)^{|T|+1}min\{T\}Ribbons on Tr ...

牛顿迭代问题描述已知函数 $G(x)$ ，求一个多项式 $F(x)\ mod\ x^n$ 满足 $G(F(x))\equiv 0\ (mod\ x^n)$ 。 Solution我们假设已经求出 $G(F_0(x))\equiv 0\ (mod\ x^{\lceil\frac{n}{2}\rceil} ...

闲扯这道题可谓是莫队的集大成者。。。 各种各样的方法都用到了。。。 题面P4074 [WC2013]糖果公园 Solution将题意简化： 每次询问树上一条路径的权值 $S=\sum_{i=1}^{m}\sum_{j=1}^{num_i}w_j\cdot val_i$ ，其中有修改操作。 如果这 ...

闲扯大家 $T1$ 怎么都会写 $O(n\log ^2 n)$ 的算法啊，为啥我只会写带 $\sqrt{n}$ 的莫队啊。。 题面2020WC集训训练赛day4 $T1$Solution 直观的想法 求出 $dfn$ ，每次修改相当于是给一个区间增加和减少一个数。 我们维护一颗线段树，在每个区间设 ...

闲扯矩阵树逐渐开始变得玄学了起来。。。 题面P3317 [SDOI2014]重建 Solution题目要求的式子： \sum_{Tree}\prod_{(u,v)\in E} P_{u,v}\prod_{(u,v)\notin E} (1-P_{u,v})如果我们将 $P_{u,v}$ 看做这条边 ...