太阁最新面经算法竞赛1题解

0
0

Problem A Difference of Interval Collections

离散化+扫描线统计 把所有端点(总计2N+2M个)按坐标从小到达排序(相同坐标的端点谁前谁后无所谓),然后依次遍历每个点P1 P[2] P[3] ... P[2N+2M]。

设两个变量Sa和Sb,遇到A集合左端点就把Sa加1,A集合右端点就把Sa减1;遇到B集合左端点就把Sb加1,B集合右端点就把Sb减1。

遍历过程中,如果P[i]和P[i+1]之间Sa>0并且Sb=0,那么p[i]p[i+1]这条线段就只被A集合的线段覆盖,没有被B集合的线段覆盖,结果加上p[i]p[i+1]的长度即可。

Problem B Stock Prices

对于P消息,我们可以用一个队列保存所有的价格和时间戳。

对于R消息,我们可以用很多方法确定删除的位置,例如O(logn)的二分查找、O(n)的hash以及均摊O(1)的从头到尾查找。

对于Q消息,等价于我们需要直到某个区间[l, r]内的最大、最小值,其中r是当前队列的队尾,l是删除了一些价格后的队首。这是一个经典的RMQ问题,可以参考http://hihocoder.com/problemset/problem/1068的讲解。

总时间复杂度O(nlogn)。

Problem C Crossing Restricted Zone

简单的计算几何+深度优先搜索

首先不存在通过路线当且仅当存在一系列圆把上边界和下边界连在一起,即存在C1 C2 C3 ... Ck使得C1与上边界相交,Ck与下边界相交,并且Ci与Ci+1相交(i=1, 2, 3 ... k-1)。

于是我们可以枚举每一个圆,先看圆和上下边界有没有交集,和上边界有交集就标记为1,和下边界有交集就标记为2,都有交集就输出“NO”。

然后再从每个标记为1的圆开始深搜,如果两个圆相交就可以互达,直到搜到一个标记为2的圆,输出“NO”。

如果最后都搜完了也没有碰见2的圆,就输出“YES”。

  • Problem C 用并查集是不是好一些?

  • 感觉并查集要好些。。

  • 添加评论
  • reply

0 answer(s)

write answer 切换为英文 切换为中文


转发分享