竞赛讨论区 > 普及周赛 26 题解

普及周赛 26 题解

头像
Feecle6418
编辑于 2021-06-04 22:22:39 APP内打开
赞 3 | 收藏 0 | 回复2 | 浏览733
A

直接判断即可,注意要变除为乘,否则所有横坐标都相同就会出问题。

B

结论:最优解要么是最左边插入一个 a,要么是最右边插入一个 b。枚举两种情况,判断即可。具体判断时,记录前面有几个 a,遇到一个 b 就加上 (a 的个数)*(a 的个数-1)/2。

需要开 unsigned long long。

C

结论:每次都选 rating 最小的最优。

堆维护即可。

D

按照以下方式建图:

新建 31 个虚点,编号为 n+1~n+31。

对于每个 a_i,若 a_i and 2^k 不是 0,从 i 向 n+k+1 连边,权值为 a_i。

显然该图与原图等价,最短路即可。Dij 或者 Bellman Ford 都能过,因为最短路的更新次数是 log 级别的。

宣传一发 http://119.27.163.117/ 题库 55~58

2条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐