日记

今天是个好日子啊。

那有人要问了：为啥是个好日子？

开心是没有理由的。

（我好中二）

Blocking Elements# Link to

我的评价是：wqs 二分（輕量化）

首先，我们找到原题，发现带了一个 二分 的标签，于是我们就考虑二分。二分出一个 $x$，dp 出当分出来的每段和都不超过 $x$，分割的那几个数和的最小值。然后判断。

这个题居然还能评 $\textcolor{3498DB}蓝$，感觉不值蓝。

Programming Competition# Link to

问啥设啥。

如上文所说，我们设 $dp_u$ 表示 $u$ 及其子树内最多能配多少对。考虑 $u$ 的重儿子 $son$。当 $siz_{son} \ge \lfloor \frac{siz_u}{2} \rfloor$ 时，一定有方案能凑够 $\lfloor \frac{siz_u}{2} \rfloor$。如果不满足，就进行转移：$dp_u \leftarrow dp_{son} + (siz_u - 1 - siz_{son})$。

Good Trip# Link to

能不用 dp 就不用 dp。

初始有 $ans = 0,sum = \sum\limits_{i = 1}^{m}f_i$，对于每一次，都有 $\frac{2m}{n(n - 1)}$ 的概率取到暧昧的硝硼铀，所以对于每次，$ans \leftarrow ans + sum \times \frac{2m}{n(n - 1)}$，且 $sum \leftarrow sum + \frac{2m}{n(n - 1)}$。

Array Collapse# Link to

做过，但是记不到。

Kim’s Quest# Link to

也记不到。

[SHOI2011] 扫雷机器人# Link to

这题的题解是真的妙。

考虑对于每个蹦蹦炸弹分开算贡献。设能够引爆 $i$ 的有 $cnt_i$ 个，那么 $i$ 一定得在这 $cnt_i$ 个里面最先被引爆才行。引爆这 $cnt_i$ 个的顺序有 $cnt_i !$ 种，它在最前面的有 $(cnt_i - 1)!$ 种。那么它被最先引爆的概率就是 $\frac{(cnt_i - 1)!}{cnt_i !} = \frac{1}{cnt_i}$。我们对于每个炸弹，设它引爆能影响 $[lb_i,rb_i]$ 的范围，$O(n)$ 往两边扩张。最后统计答案的时候，看有多少 $j$ 满足 $x_i \in [lb_j,rb_j]$。$j$ 的数量，最终答案就是 $\sum\limits_{i = 1}^{n}\frac{1}{cnt_i}$。

菜是原罪。