[POI2018]Prawnicy

[POI2018]Prawnicy
这题可以采用贪心策略,假如我们已经确定了最终区间的左端点L,那么我们选择的区间一定是左端点在L左边,且右端点最右的K个点。所以我们将所有区间按左端点排序,用小根堆维护左端点在左边,且右端点最大的K个点。每次用第K大值更新答案即可。 ......  查看更多

最短路

最短路

这题看看就是叫你建边跑最短路的,但眨眼一看,哇赛,为什么这么多边!这样明显就是为了卡SPFA了。所以我们就要用到Dij算法去解答这题,Dij算法就是让当前路径最短的那个点去找边,减少枚举情况。具体如何去找当前路径最短的点,我们可以使用堆优化的Dij算法,但是呢规模还是太大呢,自己写的堆不够高效,所以我们要采用系统配对堆进行解答。 ......  查看更多