由于是恢复训练，所以会把所有题目解法都写写。

A

显然是少的每一堆就放一个，大的尽量均摊，设 $r < b$，那么就是判断 $\lceil \frac{b}{r} \rceil -1\leq d$。

B

模拟一下发现这东西无论什么路径权值都是 $nm-1$。

证明可以考虑对 $n+m$ 归纳：首先 $n=m=1$ 是对的，考虑到达 $(n,m)$ 最后一步是怎么走的，如果是从 $(n-1,m)$ 走过来，代价是 $(n-1)m-1 + m = nm-1$；如果从 $(n,m-1)$ 走过来，代价是 $n(m-1)-1 + n = nm-1$。

所以判断是否 $k=nm-1$ 即可。

C

对于每个大学计算他的贡献，设这个大学有 $m$ 个人，发现 $k$ 确定后我们只会取前 $\lfloor \frac{m}{k} \rfloor k$ 大，所以从大到小排序处理前缀和然后对于每个大学暴力枚举 $k$ 计算贡献就好了。

D

直接暴力。重点是预处理 $f_{l,r}$ 表示 $a[l,r]$ 反转后和 $b[l,r]$ 不反转点乘的值，直接区间 dp。

E

考虑这实际上是个匹配问题：每个点有两个值 $v_1,v_2$，两个点能匹配当且仅当他们的值有交集。

根据之前惨痛的教训：看到两个值问题考虑将两个值之间连边。那么问题其实就是对边之间做一些匹配，一对边能匹配当且仅当它们在同一个点上相连。

设边的个数为 $m$，对于一个联通块，答案的一个界是 $\lfloor \frac{m}{2}\rfloor$ ，事实证明我们永远可以达到这个界。

先考虑树怎么做：我们发现如果一个子树内有没有匹配上的边，它一定可以移动到根往上的边，所以我们就可以归纳证明了：每次先递归做子树，然后把子树剩下的边在这个点匹配。

如果是图的话，就是多了一些返祖边，直接把返祖边挂在深度比较低的点上也可以类似归纳。

F

这个题比较神仙。不过如果能把限制写出来观察一下应该也会做。

先考虑如何判断 Bob 是否能获胜：发现这其实就是一个 Bob 选箱子，然后花费是和这些箱子有关联的锁。

所以锁和箱子连边，我们可以枚举箱子的集合 $S \subseteq [n]$，Bob 不可以获胜，当且仅当对于所有集合 $S$，都有：

$$ \sum_{i \in S} a_i \leq \sum_{i \in \Gamma(S)} b_i $$

其中 $\Gamma(S)$ 表示 $S$ 的子集。

发现这个非常想 Hall 定理！！1，所以我们考虑拆点，第 $i$ 个盒子拆出 $a_i$ 个点，第 $j$ 个锁拆出 $b_j$ 个点，那么这个条件等价于原图有包含左边所有点的完美匹配。

现在问题就是说，如果盒子 $i$ 的某个点与箱子 $j$ 的某个点有连边，那么就会有代价 $c_{i,j}$，要求求完美匹配的代价，那么就可以 dp 了。

dp 一开始一个 naive 的想法是记录右边的每个点有没有被选，这样状态是 $O(2^{nb})$ 的，无法通过。但是我们发现同一个锁拆出来的点本质上是一样的，所以我们只需要记录每个锁拆出来的点还剩几个，状态数就是 $O(b^n)$ 了。转移的时候枚举 $a$ 拆出的点每个匹配的谁，总复杂度大概是 $O(n 5^n \binom{n+3}{3})$ 之类的东西？反正可以快速通过。