A. Success Rate
因为最后结果一定是这个最简分数的整数倍,然后这个整数倍有个下界。发现这个整数倍可以二分,验证一下就好了。比较简单。

B. Dynamic Problem Scoring
只对于A、B都做出来的题目,并且A的分数没有B多的情况下,才有交正确程序的必要。剩下都交错误程序就可以了(或者不交)

C. Prairie Partition
思考了半天,终于猜出了答案一定是连续的结论。
知道这个结论之后,就不难了。
这个最多的表示,可以贪心贪出来,然后最少的合法表示,可以二分,然后贪心验证。

D. Perishable Roads
思考了半天,思考到了每个博物馆一定只有一个出度,然而没卵用,之后就卡住了。
看了看别人的代码,然后自己脑补了一下,乱写了一个差不多的。
先把所有的边权减去最小的边权,方便处理,这样所有的最小边权一定为0。
然后我们可以把所有点的最差结果初始化为2*最小的连向这个点的边,因为对于所有的点,最差情况下就是走两条边,然后找到了最小边,剩下的所有点的贡献就都一样了。
然后需要计算这两条边的关系,如果第二条边小于第一条边,那这两个点的贡献就是路径的长度,如果不是的话,就是2*边权。
用spfa乱算一下路径长度就可以了,反正最多只走两条路,时间复杂度应该不是问题(其实一直不太清楚spfa的时间复杂度)

发表评论

电子邮件地址不会被公开。 必填项已用*标注