NOIP2020 做题练习（day2）
A - [HNOI2009]最小圈
题面
首先二分答案。
然后把每条边的边权减去 \(mid\)，再 SPFA 找图中是否存在负环。因为存在负环就说明有平均值 \(\le mid\) 的环。
注意用栈来找负环，且要对于每一个连通块都找一遍 SPFA。
代码
B - [HAOI2010]软件安装
题面
根据依赖关系建出一张图。
然后 tarjan 缩点，这样整张图就变成了一个 DAG。
建立一个虚点 \(0\)，将它与每一个强连通分量的“代表”连一条边，这样整张图就是一棵树。
跑一遍树形背包即可。
代码
C - 排船的问题
题面
二分答案，然后贪心地每次把船尽量向左放。
代码
D - 稳定桌
题面
Codeforces 原题
首先按照桌腿长度排序，然后枚举最长的腿的长度。
开一棵权值线段树记录当前所有桌腿所消耗的能量。
记 \(x\) 表示当前枚举的最长桌腿的个数，去掉桌腿花费最少的能量就是在已经加入权值线段树的数中取最小的 \(x-1\) 个，最后记得把当前长度的桌腿所要消耗的能量加入权值线段树。
需要记一下前缀和和后缀和辅助计算。
代码