1919
CodeForces 1919F2 Wine Factory (Hard Version)
洛谷传送门 CF 传送门 题目看着感觉很像最大流,不妨建模,\(S \to i\),容量为 \(a_i\);\(i \to T\),容量为 \(b_i\);\(i \to i + 1\),容量为 \(c_i\)。答案是这个图的最大流。 考虑最大流转最小割。观察到 \(S \to i\) 和 \(i ......
CodeForces 1919E Counting Prefixes
洛谷传送门 CF 传送门 考虑一个很类似的题。我们把正数和负数分开来考虑,最后用 \(0\) 连接一些连续段,形如 \(0 - \text{正} - 0 - \text{正} - 0 - \text{负}\)。 先考虑正数。设 \(f_{i, j}\) 为考虑了 \(\ge i\) 的正数,形成了 ......
CF1919H Tree Diameter
某人在换根时根还设置成 \(1\) 交了整整 \(11\) 发,我不说是谁。 先考虑一下 \(2\) 询问的实际用途,因为我们可以用它来确定深度,根据树上交互题的常见技巧,我们通过这种方式确定了一个拓扑序,只要能在拓扑序的前缀中快速查询一个点的父亲,就可以求出这棵树。 考虑先以一条边为根,那么其会有 ......
CF1919G Tree LGM
原问题可以看作是二分图博弈的模型,那么可以将博弈问题转化为最大匹配的一定性判定性问题,实际上博弈的 \(\text{dp}\) 过程直接摊开就是每次删任意一个叶子与其父亲,将父亲变为 \(1\),这个也就是最大匹配的求解过程,而是否为匹配的上端点即该点的 \(01\) 状态,那么实际上每一行的 \( ......