【题解】2020牛客NOIP赛前集训营-普及组(第六场)

写在前面

各位辛苦啦,感谢大家。

T1 七七七七

枚举几天可以完成,然后判断。

也可以用多个if解决问题。

注意到有些同学没有考虑的情况痛失分。

T2 平面旅行

直接从走到可以获得分。

走到,并对唯一一个传送节点到达对应的点取min可以获得分。

简单建图求floyd最短路可以获得分。

预处理到达每个节点的距离,具体为所有传送门到其的距离和上一个点到其的距离的最小值,累计即可直接得到答案,可以得到分。

T3 小球下落

枚举每个小球的掉落情况,可以得到分。

模拟每个小球的掉落情况,可以得到分。

对于满分,显然从下往上贪心即可。

具体操作时每次贪心放到最下面可达的地方去,可不可达可以用规则判断。

可以发现只要有这三种情况之一就可以认为它们断开了:

xx

或者对于两层

x.
.x

或是

.x
x.

上述这三种情况会使上下区域断开,从而不可达。

可以用multiset或者其他方法动态维护最小值。

本题的时限比较宽松,复杂度小于的方法应该有很多。

T4 自由世界

简单写写if(可能不简单)可以获得分。

处理掉树上的情况+上面的特判可以获得分。

简单建图求floyd最短路可以获得分。

预处理到达每个节点的距离,具体为所有传送门到其的距离和上一个点到其的距离的最小值,累计即可直接得到答案,可以得到分。

具体的做法是以所有传送门为起点跑一次最短路(或者分开跑也行,但是控制一下常数),求每个点的最小值。

再以每个点为起点跑一次最短路,求到下一个点的最小值。

累计即可,原理上这样可以获得分,但可能因为常数原因会损失一定的分数。

下面是四题的标程:
T1: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45401125
T2: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45401131
T3: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45401136
T4: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45401148

全部评论
想问一下博主,第四题Dijkstra复杂度为(mlogn),再套上n的循环,总时间复杂度为(mnlogn),根据数据范围为什么不会超时呢?
点赞 回复
分享
发布于 2020-10-29 22:44
求助, B 题为什么只要对传送门和前一个做松弛操作啊?谢谢
点赞 回复
分享
发布于 2020-10-30 21:06
百信银行
校招火热招聘中
官网直投
是由于曼哈顿距离使得三个不是传送门的点满足三角形不等式的性质吗?
点赞 回复
分享
发布于 2020-10-30 21:08

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务