链接 & 题目大意 算法 & 数据结构 差分、单调队列 思路 & 推导过程 暴力 1 注意到我们可以直接模拟，但是这样的话复杂度很难优化，没有前景，需要考虑换一个暴力。 暴力 2 注意到我们需要统计每秒牛奶的浪费，所以可以想到一个奶牛在 $k$ 秒后传入的牛奶是前 $k$ 个奶牛容量的最小值，而只有当这个最小值大于当前奶牛容…

链接 & 题目大意 P6146 Help Yourself G 算法 & 数据结构 计数，DP 思路 & 推导过程 首先可以考虑如果把一个线段加进去会出现什么事情。 我们先想到可以考虑 dp[i] 为包含第 i 个线段的答案为多少，但是发现这样会算重，很难处理。 那只能换个思路，也就是令 dp[i] 表示加了这个线段后的答案…

思路 90pts 注意到 $O(n^2)$ 的暴力的能得到 90pts，不妨先考虑一下这个该怎么写。 我们可以考虑 dp，令 dp[i] 为到 i 的时候的最少的答案。 我们可考虑要从 dp[j] 扩展到 dp[i] 只有两种方法，第一种方法也就是在最后一次买东西的时候把羊毛都没买好，后面的直接走到目的地就行了。 第二种方法，就是在走到 j 后走回…

分数：100 + 40 + 25 + 8 = 173。 T1 调试花了过多的时间，一共调 5 次，每次都是过了小样例过不了大样例，每次都修改了一些，最后 AC 了，一共花了 2.5 H T2 想了一个假做法，复杂度和正确性都不对，过了除了最后一个大样例外的所有样例。做法是跑 MST，然后遍历每个乡村考虑能不能用乡村中转来替换目前的这条边，但是这个方…