竞赛讨论区 > 【题解】牛客小白月赛16
头像
xuxuxuxuxu
编辑于 2019-07-16 20:02
+ 关注

【题解】牛客小白月赛16

A-小石的签到题

我们发现当 时先手(小石)总是赢。
如何证明:一开始有 , 个数,假设先手必败,那么先手选 ,后手就进入了必败状态。
所以假设错误,那么先手就不是必败,先手一定有一种方式能赢。

B-小雨的三角形

数据范围给的很小,可以 暴力构造三角形,预处理出每一行的总和,每个询问把 行的和加起来即可(若预处理出第 行的和,则可以做到 查询)。
更快的做法?每一行的和其实是有规律的,分别为 ,除了第 行的和为 外,第 行的和为 ,那么第 行的和为

所以第 行的和就能用前缀和计算了,注意特判 的情况,这样就能够每次 查询。

C-小石的海岛之旅

我们按海岛的高度 从大到小排序。
假设海岛在水位为 时被淹没,如果海岛 和海岛 都已被淹没,那么就少了一块,答案减
如果海岛 和海岛 都没被淹没,那么一块变两块,答案加
否则答案不变。
由于出题人良心,直接是能过的。

D-小阳买水果

我们要发现单调性,如果这个区间符合条件,那么左端点变为 的话,
右端点只有变大才有可能可以更新答案。所以就是每次右端点要变成可能中的最大值。
右端点每次从 枚举找最大值不现实,
我们考虑优化,记录一个后缀的 数组,每次跳 即可。

E-小雨的矩阵

送分题,从爆搜到,把答案去一下重即可。

F-小石的妹子

我们发现妹子们之间是有拓扑的关系的,比如妹子,她一定只能在都比她大的妹子的后面。
所以 的做法就是暴力连边,然后拓扑求解,
满分做法:
这不就是二维数点问题,咋做都对啊。
因为有两维的限制,所以我们先按 从大到小排一下序,
对于排序后的第 个妹子,她的排名就是
那么我们把排名 当成下标,把 当成值,用线段树维护一下区间 即可。

G-小石的图形

发现半圆时面积最大(显然)。
面积

H-小阳的贝壳

区间 具有结合律,很容易用线段树维护,考虑如何区间修改。
首先要知道 的一个性质:

所以我们可以在线段树上建立差分数组,维护 区间和 与 区间
显然区间 就是 ,其中 表示差分数组。
至于第 个操作完全就是来搞笑的(主要用来引导别人联想到差分),只要维护差分数组的区间 和区间 就行了。最后的答案就是 区间 与 区间 相反数 的较大值。

I-石头剪刀布

简单的 期望DP+高斯消元 表示从 走到 的期望步数。

直接高斯消元是 ,能过。
但可以有更优秀的做法:
发现 之和 和一个常数项有关,
是稀疏矩阵,直接手动高消(即不要 循环,直接把要消元的消一下即可)

J-小雨坐地铁

考虑分层图最短路。
很容易想到建 层图,如果多条地铁线都经过同一个点,则在这些点之间暴力两两连边,这样连边是 的,可能会超时。
我们可以多建一层虚点,所有点到它对应的虚点不需要代价,从虚点到它对应的点需要对应的代价,这样就可以优化到 建图。最后跑一边最短路就好了。

标程
A:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40835584
B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40835585
C:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40835588
D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40835589
E:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40835590
F:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40835591
G:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40835593
H:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40835594
I:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40835596
J:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40835597

全部评论

(10) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐