竞赛讨论区 > 【题解】2021牛客OI赛前集训营-普及组(第六场)
头像
Trote
编辑于 2021-10-16 23:00
+ 关注

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

普及组题解

A 月相

需要判断的是接下来会变大还是会变小,不如先顺着前面的节奏走,即得到 b+(b-a) ,如果结果为 16 或 -1 ,大于0~15的范围,则考虑变为 14 和 1 即可。

其余情况使用直接得到 b+(b-a) 即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49022113

B 间隔

需要注意的是有一些 case 需要讨论:

正好成等差数列的情况(尤其是全部相同的情况),不需要插入元素,结果为0。

以及样例里的部分 相等的情况(结果为-1)。

考虑了这些情况之后,暴力枚举差值就可以获得满分,时间复杂度为:

约等于

更进阶的做法是:特判了一些 case 之后,本质是一个求相邻元素的 gcd 的问题。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49022111

C 密码锁

完全暴力应该比较容易获得分。

dfs/bfs计数+剪枝可以获得约分。

定义状态为(当前按钮位置, 当前密码输入到第几个),显然需要枚举范围内的所有可能性,状态数 ,转移复杂度 ,故时间复杂度为 。缓慢的写法可以得到约分。

在真实数据上,稍加剪枝(或卡常)即可通过。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49022109

此外,暴力枚举做一些处理,使复杂度变为

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49022251

D 上街

对于没有红绿灯的情况,直接使用最短路算法即可,可以得到 分。

对于小范围的地图,可以考虑暴力搜索,有很多逼近正确答案的技巧,甚至随机搜索也可以得到一定的分数。

考虑如何建图:

因为所有红绿灯的总时长都是相同的,可以考虑将红绿灯的相对时间(时间 mod 红绿灯总时长)编码到当前状态中,当前状态为(红绿灯的相对时间,当前路口, 当前朝向),这样的状态可以唯一表示,当前路口可以直接使用 的方式编码,朝向0上1右2下3左。

如果在每个路口之内转移,可以将“是否已通过路口”加入状态,(红绿灯的相对时间,当前路口,当前朝向,是否已通过路口(0=未通过,1=已通过))。初始状态为(0, (1,1), 朝下,未通过),即(0,0,2,0)。设到状态的最小代价为

接下来开始详细讨论状态转移:

如果已经通过一个路口,就可以向下一个路口前行了,设为下一个路口,为这段路程的距离,即

接下来考虑通过路口,向右转的情况相对比较简单,

向左和向前需要考虑是否需要等待红灯,等待红灯的时间需要额外计算,设需要等待 秒,代价为 。即

以上,我们已经完成了对整个状态转移的讨论,因为状态转移中存在环,对于最短路的寻找需要依赖最短路算法而不能是有向无环图(DAG)的求解。

此外,注意到通过路口后,一定会前往该方向的下一个路口,所以事实上可以删除状态中的“是否已通过路口”,可以节约大约相当大量的时间。

最短路算法中,点数为 ,边数为 ,使用的最短路算法可以通过本题。

P.S: 本题因为造数据的技术原因可能没有卡住SPFA,并由此作者感到了恐惧。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49022106

全部评论

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

等你来战

查看全部

热门推荐