Round 1
调配
我们设 \(f_{i, j, k}\) 为到 \(i\) 总和为 \(j\) 且选的个数为 \(k\) 的方案数，显然背包转移，然后最后算答案算个平均值即可。
运输
我的赛时想法是在 dijkstra 维护 DP 数组 \(f_{i, j}\) 表示到了 \(i\)，最小边权为 \(j\) 的最短路是多少，但是注意到边数很多，点数很少，本质上有相当多的状态是无用的，我们用 set 来维护这些状态，每次松弛一个点时顺便把无用状态给删掉。具体复杂度未知，但能过。
题解做法是跑 floyd 从小到大加边做，但说实话我没看懂。
考试
公式化做题就是快。
考虑概率互不影响，我们把所有 \(l_i, r_i\) 给分割成一个个区间，依次考虑每个数在哪些区间里，考虑把剩下的数分为 \(2\) 类，一类是在这个区间之外，一类是在这个区间之内，DP 是很容易的，但是你发现复杂度是 \(O(n^5)\)，很不好。
每次对于枚举区间相同的情况，我们其实都是扣掉一个位置做背包，我们将 DP 转移换元后即可发现是可以删除某个位置的元素，因此 \(O(n^4)\) 做完了，需要注意当 DP 转移系数是 \(0\) 的时候就不能将对应的那项作为主元进行撤销了，因此 \(3\) 个系数都得跑一遍。
网络管理
假设只有 \(2\) 操作怎么办。
显然，我们可以以 DFS 序为一维限制，深度为一维限制，做二维数点求和解决。
那么，我们加上 \(1\) 操作怎么办，我们可以新加一维时间维，用 CDQ 分治离线解决。
最后考虑如果有 \(3\) 操作怎么办。
这个问题被转化为了二维平面矩形加，矩形查，可以用二维分块或者直接使用 KDT 达到根号的复杂度，同时由于可以离线，KDT 不需要二进制分组了，直接离线先建完就好。