实习与工作

PayPal实习生笔试

jxtxzzw · 4月1日 · 2019年 · · · 80次已读
文章由jxtxzzw原创

有点难。这是jxtxzzw的个人博客

简单模拟就好了这是jxtxzzw的个人博客

Copyright Reserved @jxtxzzw

一开始以为是聚类。

后来知道是并查集。

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

输出这是jxtxzzw的个人博客格式感觉是专门为 Python 定制的啊,很鄙视。

输入:

并查集:

https://www.jxtxzzw.com

Point 是一个类。

输出:

这道题我觉得有点难。

一开始以为是贪心或者什么,后来请勿采集与复制,转载请注明出处想想是不是线段树,但是显然线段树求区Copyright Reserved @jxtxzzw间最值、区间和,没法维护每一段的状态。

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

https://www.jxtxzzw.com开始他给出的是差分维护,就是遇到左端点 +1,遇到右端点 -1,找最大区间。

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

第 2 个https://www.jxtxzzw.com样例的输出是

 1 2
 2 3
 3 4
 4 5

也就是弹幕最多的时间是 4 段,每段都是 1,不能合欢迎访问jxtxzzw个人博客并的。

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

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

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

最后一题是 DP。

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

题目是说给你 反采集功能启动K 架飞机,测试最大拉伸高度。

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

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

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

关键的部分是 DP。

就是 ​$f(h, k) = min_{0 < i \leqslahttps://www.jxtxzzw.comnt h } { max{f(i,k-1), f(n-i-1,k)}} + 1​$

0 条回应