最近完成的一些算法题

一个多月没写博客了,赶紧填个坑。

kickstart
离上一篇博客居然已经过去一个多月啦,看来研究生还是要比本科忙多了,每天都有事情要做。最近呢,就是参加了昨天的 Google Kickstart Round G 2018,本来顺利做完了 2.5 题,做完的时候有 60 名左右,结果有个大数据犯了一个低级错误,结果一个大数据挂了,最后只有 100 多名!啊!好气啊!看了一下题解,发现方法和我自己实现的方法差挺多的,所以想简单讲一下我的算法。

Problem A. Product Triplets

这道题,就是给你一个序列 $A_n,n\leq7000$,让你计算满足 $A_i,A_j,A_k$ 三个数中任意两个数乘积等于第三个数的这样的 $(i,j,k) , i \lt j \lt k$ 三元组的个数。

题解中给出的方法是使用 HashSet 存入每个数,同样也可以使用二分。注意到序列的顺序无关,因此我们可以先将数列排序,然后枚举 i 和 j,注意到在绝大多数情况下,$A_i*A_j \geq A_i,A_j$。因此我们要找的乘积一定在 $A_i$ 和 $A_j$ 的右边,而由于整个序列是有序的,因此我们可以通过二分来快速找到相应的值,伪代码如下所示。

1
2
3
4
for i = 1 to n
for j = i + 1 to n
binary_search A [i] * A [j] from A [j + 1] to A [n]
answer ← answer + count (A [i] * A [j])

由于我们需要求出序列中 $A_i * A_j$ 的个数,因此在 C++ 中,可以分别调用 lower_boundupper_bound 来求出上界和下界,然后相减即可求出个数。

前面提到在大多数情况下 $A_i*A_j \geq A_i,A_j$ 是成立的,那么是否有不成立的情况呢?有的,在 $A_i=0$ 或者 $A_j=0$ 的时候等式就不成立了。这个时候三元组对应的序列就变成了 $(0, 0, A_k)$。因此在排好序的序列中,我们需要特判 $A_i$ 和 $A_j$ 都等于 0 的情况,可以计算得出此时三元组的个数恰好为序列中所有在 $A_j$ 右边的元素的个数。也就是 $n - j$。整个算法的复杂度为 $\mathcal {O}(n^2\log n)$

Problem B. Combining Classes

这道题,是给你 $N$ 个 $[L_i, R_i]$ 连续区间组成的分数,然后有 $Q$ 个查询,问这些区间中所有数字组成的序列的第 $K_i$ 大的分数是多少,其中 $N$ 和 $Q$ 的范围都在 $5*10^5$ 级别。

题解的方法是离散化 + 线段树区间维护,似乎有一些麻烦。实际上可以直接将区间拆成 $2N$ 个点,然后从大到小排序。接下来就是处理区间端点的问题了,再遍历断点的过程中,我们需要一个变量 $cur$ 用于记录当前分数有多少个人同分,$sum$ 记录目前总共排好了多少个人,这样在遍历的过程中不断的将 $K_i$ 和 $sum$ 进行比较就可以了。另外需要注意的是,在遍历过程中如果端点的发生了跳跃,我们需要直接算出 $K_i$ 对应的分数,方法就是计算 $sum$ 与 $K_i$ 的差值,然后整除 $cur$ 即可。整个算法中,排序复杂度是 $\mathcal {O}(N\log N+Q\log Q)$,遍历的复杂度是 $\mathcal {O}(N+Q)$

评论