本文写于 2019年04月01日,距今已超过 1 年,距 2020年03月27日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

有点难。

简单模拟就好了。

一开始以为是聚类。

后来知道是并查集。

甚至不需要路径压缩等技巧,裸的并查集,直接开长度为 N 的数组,每次要合并的时候遍历,修改需要合并的所有值为 p 的改为 y 就行了。

输出格式感觉是专门为 Python 定制的啊,很鄙视。

输入:

并查集:

Point 是一个类。

输出:

这道题我觉得有点难。

一开始以为是贪心或者什么,后来想想是不是线段树,但是显然线段树求区间最值、区间和,没法维护每一段的状态。

考试结束以后问 zerol,他说不可能是线段树这么难的,肯定是简单算法。

一开始他给出的是差分维护,就是遇到左端点 +1,遇到右端点 -1,找最大区间。

后来看到样例 2,就感叹我抽题的运气不好。

第 2 个样例的输出是

 1 2
 2 3
 3 4
 4 5

也就是弹幕最多的时间是 4 段,每段都是 1,不能合并的。

而且题目是开区间,很诡异。

林的建议是,加一个 .5 区间,搞成左开右闭或者左闭右开,这样就把开区间的问题解决了,可以差分了。

但是第 2 个样例输出 1 5 还是分 4 段,还需要考虑。

最后一题是 DP。

大概的提示和扔鸡蛋测试最高每个鸡蛋能扔多高是一样的。

题目是说给你 K 架飞机,测试最大拉伸高度。

样例 1 是 1 架飞机,1000 米,那就必须测试 1000 次了,因为飞机损坏了就没有了。

样例 2 是 15 架飞机,1000 米,由于飞机足够,用二分。

其实这两个特殊状态出去已经有一些部分分了。

关键的部分是 DP。

就是 ​$f(h, k) = min_{0 < i \leqslant h } { max{f(i,k-1), f(n-i-1,k)}} + 1​$

0 0 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论