BNU-2017.7.5排位赛3总结

链接:https://www.bnuoj.com/v3/contest_show.php?cid=9148#info

A题

满足条件的只有(1,2,4),(1,2,6),(1,3,6),所以先满足4,剩下的满足6,如果还有剩下的或者不够就不行。

B题

for一遍1到6即可。

C题

论半场排名,肯定是每个半场的前一半都有机会。

论所有排名,k=0的时候,所有人中的前n名有机会。如果在k=0的时候没有机会,也就是意味着排名在[n+1,2n],那么k=2的时候,所有人中前n-2名有机会,在k=0没有机会的人,在这里最多在[n-1,2n-2]名,所以还是没有机会。也就是说,k=0没有机会的,后面肯定也没有机会了。所以只看k=0即可。

D题

一个大水题当时居然没读。。。能传就传,贪心模拟即可。

E题

边权相等的最短路,转化成BFS。O(n)求一次单源最短路,求n次即可。

F题

二维树状数组板子。

G题

2-SET+强连通分量,简直是绝配。

H题

后缀数组,待学习。

I题

区间DP,组合数用逆元打表的时候爆ll了。。调了很长时间。

原文地址:https://www.cnblogs.com/acmsong/p/8157338.html