最近完成的一些算法题

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

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)$