7 年前发表学习笔记 / 算法笔记6 分钟读完 (大约955个字)25次访问

最近完成的一些算法题

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

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

Problem A. Product Triplets

这道题，就是给你一个序列 $A_{n}, n \leq 7000$ ，让你计算满足 $A_{i}, A_{j}, A_{k}$ 三个数中任意两个数乘积等于第三个数的这样的 $(i, j, k), i < j < k$ 三元组的个数。

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

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_bound和upper_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$ 。整个算法的复杂度为 $O (n^{2} \log n)$

Problem B. Combining Classes

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

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