divide and conquer

[caibirdme]

这类题主要在于如何划分子问题

[caibirdme]

Different Ways to Add Parentheses 如果一开始就想到构造括号的位置再进行计算就这题就没法做了. 想一想, 其实添加括号的本质就是改变运算符的优先级. 也就是说, 添加括号本质上就是决定先算哪个再算哪个最后算哪个. 因此我们可以枚举最后一次运算. 我们找到一个运算符, 然后把字符串拆成3部分 (....) op (....). 每个部分假设进行计算后所有不同的结果都保存在arrX和arrY, 那么最终可能的结果就是each(arrX) op each(arrY). 计算各个部分的结果, 就是相同的子问题.通过这种方式我们避免了直接对括号进行构造

如果进一步优化, 我们发现很多子问题我们进行了大量重复计算, 因此可以利用记忆化记录s[i]..s[j]的结果. 然后这道题稍微改一改, 还可以问, 通过加括号有多少种不同的计算结果, 我们只需要把vector改成set即可.

分治法的关键在于, 想办法减小问题规模, 划分出相同子问题. 通常需要逆向思维---枚举最后一次操作.

[caibirdme]

Count of Range Sum 连续区间和首先应该想到的就是利用sum(i)-sum(j)这种方式来进行求解. 这道题也不例外, 先求出所有sum. 然后有两种方法. 要求连续区间和满足 low <= sum(i)-sum(j) <= high, 相当于:

sum(i)-low >= sum(j)
sum(i)-high <= sum(j)

因此, 第一种方法就是, 枚举每个sum(i), 在它之前去找到一个最大的sum(j) 满足, sum(i)-low >= sum(j). 同时, 再去寻找一个最小的sum(k), 满足sum(i)-high <= sum(k). i-j+1即为以sum(i)为右端点符合要求的区间数. 我们可以利用某种数据结构维护一个有序的列表, 从而可以在logN的时间内找出lower_bound和upper_bound. 这种数据结构在C++中就是multiset. 或者自己手动实现一个平衡二叉树(带size的BST可能退化成N^2)

另一种方法就是归并排序, 这个可能一开始比较难想到. 我们对sum数组进行归并排序, 在merge两个数组之前, 我们有两个有序的数组A和B. 这时, 对于A中每一个元素, 假如它作为目标区间的左端点, 我们尝试找有多少右端点满足. 即B中有多少元素满足 low <= B[j]-A[i] <= high. 看起来可以二分, 但是还有更简单的方法! 假如我们在B中找到了一个最小的j和最大的k, 使得B[j..k]中所有点都可以作为A[i]的右端点. 这时我们可以确定有j-k+1个以A[i]为左端点的区间满足要求. 那么对于A[i+1]呢? 仔细想想, A是升序的, 因此B[j]-A[i+1]<=B[j]-A[i]. 因此如果A[i+1]作为左端点, 那么B中的最小值只可能在j之后, k同理. 因此当固定左端点之后, 不需要再次从B[0]开始找合法的右端点. 把上一次的j k指针接着向后扫描即可. 因此merge一个长度为M的区间, 同时求出所有合法区间的复杂度是O(M). 确定完合法区间后, 再进行归并操作即可.

这样总体复杂度就是nlogn.

通过这道题, 我们得出一个结论, 熟悉各种数据结构和STL的用法, 可以大大减少做题消耗的脑细胞, 否则需要去想各种取巧的方法. 掌握STL中multiset尤其重要, 很多题都需要在logN的时间内求lower_bound和upper_bound这样的操作

[caibirdme]

Reverse Pairs 这道题和上面题是一样的, 本质上就是逆序对的变种. 对于逆序对, 我们常用的办法就是归并排序. 在归并时, 由于两个部分都有序, 而题目要求是A[i]>2*B[j], 因此在进行归并之前想办法求出所有符合条件的即可. 而且与上面题目类似, 由于各自部分都具有单调性, 因此当B[j]固定时, 我们可以找到一个最小的A[i], 使得A[i]>2*B[j]. 对于B[j+1], i只可能更大. 所以,也可以通过O(M)的时间求出结果. 总体时间是nlogn

另一种方法是树状数组. 利用树状数组可以很方便的统计区间内数的个数. 我们顺序枚举每个数A[j], 由于我们要找i < j 且 A[i]>2A[j], 因此, 我们需要找 A[j]之前有多少数大于A[j]2. 那么利用树状数组, 我们可以统计出有多少数小于等于v, 利用总数减去这个值就是大于它的数的个数.

但是题目中的数值范围很大, 因此我们需要对数进行离散化. 离散化的核心就是把出现过的数值按照它们的大小顺序映射成1..T. 假如用hash(x) = y来表示原来的x经过离散化之后变成了y, 那么当我们往树状数组插入一个数x, 实际上就相当于在位置y插入元素. 由于我们需要找大于x*2的数有多少, 因此我们在离散化时还要把每个数的两倍一起处理.

[caibirdme]

Beautiful Array 这道题还是稍微需要一些思考的. 由于不能存在i<k<j时存在a[i]+a[j]=2*a[k], 有一个比较容易的办法: 根据观察, 2倍A[k]一定是一个偶数, 那么如果A[i]和A[j]一个为奇数一个为偶数肯定就能够使它们不相等. 假如我们把奇数都放到左边 偶数放到右边, 即

奇1 ... 奇k 偶1 ... 偶k

• 最右边的奇数k和右边所有(偶)数之间, 都不可能存在a[i]+a[j]=2a[k]的情况.
• 偶1和左边所有数也不存在a[i]+a[j]=2a[k]

但是不能保证奇1..奇k内部不存在, 偶数内部同理也不保证. 如果我们继续分别调整奇数部分内部和偶数部分内部, 使他们不存在这种关系, 那么一切就解决了.

这里有个小推论, 假设数组A是个beautiful数组, 那么把A中每个元素x都映射成kx+b后, 新的数组依然是beautiful数组. 可以用反证法证明: 假如新数组存在a[i]+a[j]=2*a[k], 由于a[i] = K*X2+b a[j]=K*X2+b a[k]=K*X3+b, 则有 K*X1+b+K*X2+b=2*K*X3+2b => x1+x2=2*x3, 这与题设的原数组为beautiful数组相悖

有了这个推论之后呢, 对于奇数部分 1 3 5 7 9... 我们可以想办法把它们映射到1..n, 因为这样就又变成了相同子问题. 所以可以对每个数加一再除以二. 同理偶数部分可以把每个数除以2, 也变成相同子问题了. 接下来就递归即可.

由于题目规模N小于1000, 因此最大递归层数logN为10, 不需要再额外去进行记忆化了.

---

这道题和Elimination Game非常相似, 把一列数从左到右删除奇数项, 再从右到左删除剩下的奇数项, 问最后剩下哪个数. 一样的做法, 首先删除完奇数项之后, 只剩下偶数项了, 那么我们可以把所有偶数项都除以2, 又变成1..k了.只不过这时换成从右边开始删, 我们可以再构建一个helper函数, 来返回从右边开始删最后剩下的数. 当从右开始删时,如果一共有偶数个数, 那么最后将剩下所有奇数项, 我们依旧可以使用(+1)/2的方式来映射.

[caibirdme]

K Closest Points to Origin 这道题如果抽象一下就是寻找数组中的前k小(不要求前k小的顺序). 朴素方法就是排序, 取前k (NlogN), 或者用大顶堆, 维护一个capacity为K的大顶堆, NlogK. 然而还有一种更好的方式, 就是利用快排进行小改进. 由于快排每次会找一个基准piv, 把小于等于piv的放到左边, 大于piv的放到右边, 因此当一次扫描结束时, 我们能够确定有多少个数小于等于piv. 假如有t个, 而题目要求的是前k小, 那么如果t小于k, 就继续在(l..j-1)之前继续排序, 否则呢, 就可以到(j+1..r)去找前k-t小. 这种方法可以避免不必要的排序(因为只要前k小, 不关心它们的顺序)

[caibirdme]

Number of Ships in a Rectangle 这道题其实就是一个很简单的四分, 但是更简便的实现方式是二分. 但是这道题我卡了很久, 主要是因为矩形的切分方式... 如果把一个大矩形切成4块, 我们可以先求出重点坐标(mx, my), 然后很容易计算出4块小矩形各自的左下角和右上角. 但是这里我出了一个问题! 我把{(rx, ry), (mx, my)}当成的右上角矩形, 这样表面上看起来没问题, 但实际上会陷入死循环. 比如(1,1)(0,0), 找中点(1-0 / 2, 1-0 /2)=(0,0), 然后又把(1,1)(0,0)当成了右上角, 这样就死循环了! 正确的方式是把(rx,ry)(mx+1, my+1)当成右上角. 这其实就二分是一样的, 由于我们除以2是向下取正, 所以最终当l+1==r时, mid一直就是l, 这时我们就不能把区间分成(l, m-1)和(m,r), 而应该是(l,m)(m+1, r). 因此二分的正确姿势也应该是:

if xxx() {
  l = m+1;
} else {
  r = m;
}