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

写在前面

T2的语言组织非常欠妥,十分抱歉。

T1 袜子分配

注意题目要求误差需要小于,如果直接输出保留的位数不够多会扣很多分。

暴力可以获得至少分。

定义d[i][j]表示现在有个单只袜子,有对双只袜子到取完的数学期望。

每次取时可以枚举拿第一只和拿第二只的情况,可以在O(1)的时间复杂度下转移。

故时间复杂度为,可以得到分。

开始时,有种不同的取法,只有种拿法可以获得快乐值。

可以通过数学推导或者观察得出结论:

对于,答案为

T2 艰难睡眠

本意是处理一个环上的问题。但是题目描述好像给大家造成一定困扰,再次抱歉。

考虑枚举牛牛睡觉的时间,相当于需要对每个人取睡觉不干扰牛牛部分的最小值。

暴力获取大概可以获得分或更多。

可以用multiset预处理区间最小值,或者用某些数据结构在线维护。

时间复杂度。这样显然只能获得大概分,因为这个那么夸张。

用单调队列或是其他的做法来解决问题可以获得分。

T3 路径难题

考察最短路和构图技巧。如果是独立思考的结果的话,证明你已经有点懂最短路了。

如果无视公交车的话,可以得到分。

每个公交车建条边的话,大概可以得到分?

构图上考虑将每路公交车构造一个点:让该路公交车对应的所有站台都有向边连接到它;它通过有向边连接到该路公交车对应的所有站台。然后跑dijkstra即可。因为单次打车和多次打车有舍入上的出入,所以需要维护一个下一次收费的距离,如果坐公交车就清空该距离。

这样的话时间复杂度是O(m\log m)级别的。

T4 牛半仙的妹子序列

作者:hahahahahahahahah

把题目转化为对一个极长上升子序列计数。

一个子序列 是极长上升子序列,当且仅当不存在一个不同于 的上升子序列 ,且 包含 中所有的元素。

表示以第 个位置结尾的子序列的极长上升子序列个数。

考虑从前往后 DP。

考虑怎样的j能够转移到 ,在位置 之间不存在比 大且比 小的数,如果只考虑“比 小”这个限制,可以建一个权值线段树,含两个标记,一个为是否能产生贡献,一个为贡献的大小,每次更新对应权值,查询只需查询目前加入的小于当前数的权值,单次复杂度

考虑加上“比 大”这个限制,当出现一个权值被夹在中间的数之后, 就不能贡献了,于是我们考虑一个线段树区间取 的操作:将能否产生贡献的标记改成一个权值 ,在扫完原数列的一个数 后,将 赋为 ,在查询第 位的答案时,先将线段树 的所有点的 ,线段树 中的 等于 的数的贡献和即是答案。

考虑如何维护线段树取 ,记录一个 表示区间最大, 表示区间严格次大。若区间取 的值大于等于 ,return;若 ,修改 和对应贡献,打个 ;否则就暴力递归处理,一次暴力递归复杂度是 的,一次递归 的种数会至少减 ,而种数是 的,所以总时间复杂度

全部评论
楼主,有代码吗?
3 回复
分享
发布于 2020-10-30 08:51
T1的数学推导可以发一下吗..
2 回复
分享
发布于 2020-11-03 19:35
百信银行
校招火热招聘中
官网直投
T2 写的好的话,暴力 O(nm) 可以过掉#7 #8 的。还跑的飞快(但是你把题面改了呀喂
点赞 回复
分享
发布于 2020-10-29 22:38
此外 T1 可以 OEIS A155519
点赞 回复
分享
发布于 2020-10-29 22:39
说错了 是 O(nm^2)
点赞 回复
分享
发布于 2020-10-29 23:09

相关推荐

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