开个帖子记录自己刷挑战程序竞赛的历程

开头：版主能不能让我编辑一下之前的帖子，因为[ i ]被解释成斜体导致出了很多格式上的错误，而且内容也不对了，看了感觉十分崩溃。。
今天三道基本都是模板题，轻松水过。

POJ 1742: Coins

有n种硬币，每种硬币有其个数限制以及数量限制，问组成m的组法

思路：多重部分和问题模板，一模一样。。。

POJ 3046: Ant Counting

有T种蚂蚁共A只，每种蚂蚁有Ni只，同种蚂蚁不能区分，不同种蚂蚁可以区分，记Sumi为i只蚂蚁构成不同的集合的方案数，问 Sumk（S≤k≤B）之和。

思路：多重组合数的模板题，一模一样。。。但是注意这题一个大坑！最后结果需要余10^6. 但是这种情况下需要注意c++和python不一样，计算过程中分分钟可能给你溢出。因此需要注意在结果需要求余M的情况下：  (1) 加法运算后立即求余，避免溢出；(2) 减法运算小心减出负数！先加上M再求余数！

POJ 3181: Dollar Dayz

给N元钱，以及价格分别为 1->K 的无限种商品， 问有多少种方法可以刚好花完这N元钱。

思路：完全背包的模板题，一模一样。。然而死活通不过。上网找了了一圈发现特么这题考点在于大数，就是结果可能非常大，需要自己写大数的运算，例如相加，输出等。因为这里我的目的还是掌握dp算法，在确保dp部分思路正确后抄了一个大数运算交上去了 :-)

charleszhou 发表于 2019-2-21 12:05
开头：版主能不能让我编辑一下之前的帖子，因为[ i ]被解释成斜体导致出了很多格式上的错误，而且内容也不 ...

很抱歉给你带来这多麻烦。还请以后paste之前做最后的search and replace应该不花时间但是仍然是个麻烦。规则就是把

1. 修改规则就是把
   
2. [i]
   
3. 全部replaceall成
   
4. [ i ]
   
5. 否则[i]会被解释成斜体。
   

复制代码

我看楼上只有四楼需要修改。无法让你自行修改，我会尽快帮你修改。

charleszhou 发表于 2019-2-15 00:31
例题：

POJ 3617：Best Cow Line

18垅已经改过了。你看看有无问题。如果没问题我就照此把另外三个楼层该过。

14417335 发表于 2019-2-22 06:46
18垅已经改过了。你看看有无问题。如果没问题我就照此把另外三个楼层该过。

感谢版主！！修改的非常完美哈哈

POJ 1065: Wooden Sticks

题意比较复杂，不过概括一下就是给N个 pair <int, int>, 把pair分成x组使得每组里的pair第一个数和第二个数都是递增的, 求最小的组数(x值)

思路：这种的思路是首先按照第一维排序，然后就可以只考虑第二维的情况了。我们考虑贪心算法，假设 dp[ i ] 为到第i个pair为止的最长序列。那么是不是可以设 dp[ i ] = max{dp[j] + 1 | 0 <= j < i}呢？可惜这种做法是错误的，这里毕竟不是找最长上升子序列，而是找把数组分成若干个上升子序列的最小划分组数。一种正确的贪心策略是从第一个pair开始往后找，合并所有能合并的pair, 一轮完成后组数 +1, 最后直到所有 pair都处理完，这样时间复杂度是 O(n^2)

这题的神奇O(NlogN)做法要用到Dilworth定理。把一个数列划分为上升子序列的最小分法，等于这个数列最长(严格单调)下降子序列的长度。。反正我是没懂。。不过写了一下果然能 AC。。。

POJ 1631: Bridging signals

在位置i上有数字A[ i ]。左边的i号点在右边连上A[ i ]点，问最大的不相交边数

思路：这题看上去很吓人，但是稍微画一个例子立刻就能发现其实这题本质上就是求LIS.

POJ 2392: Space Elevator

n件物品，第i件hi高，有ci件，最高的一件不能超过ai的高度。问最高能堆多高

思路：有人在下面说了一句，差不多是裸的多重背包问题。一看果然如此。不过这题的关键在于我误会了ai的作用。最开始我以为是说每个物品不超过ai就行了，后来才发现ai是物品i能达到的最大高度。因此这里我们需要先对ai进行排序－首先处理那些最大高度限制比较小的物品，其他部分就和多重背包一模一样了。

POJ Making the Grade

给一列数A，问最小代价将其变成单调递增或者递减的。将数A[ i ]变成x的代价为 abs(A[ i ] - x)

思路：VMware最难的一套 OA 里面有这题。最开始一看就觉得稍微思索一下即可识破做法：我们用dp[ i ][j]来表示把前i个数变成non decreasing，同时把A[i-1]变成A[j]的最小cost。于是我们有：

dp[ i ][j] = abs(A[i-1]-A[j]) + min(dp[i-1][k] | 0 <= k <= j, A[k] <= A[j])

然后一提交 TLE ! 但是怎么想都觉得如果按照这个定义方法这个O(N^3)的复杂度是免不了的。后来偷喵了一眼题解才恍然大悟。这里之所以需要做第三层循环主要是因为A的排列不是递增的。但是我们可以新建另一个数组B,B是A的有序排列。用dp[ i ][j]来表示把前i个数变成non decreasing，同时把A[i-1]变成B[j]的最小cost。这样我们有:

dp[ i ][j] = abs(A[i-1] - b[j]) + min(dp[i-1][k] | 0 <= k <= j)

也就是说我们只需要记住 min(dp[i-1][0:j])的最小数即可，这个过程可以优化到O(1), 这样总的复杂度就是O(N^2)了。

POJ 2184: Cow Exhibition

N个 pair <ai, bi>, 求这些pair的总和sum（ai + bi) 最大值，但是限制 sum(ai), sum(bi) 都不得小于0

思路：这题能A真是有点喜出望外。让我们来看一看我最开始的错误思路。首先这个题目是稍微变化了一点的背包。我们可以定义 dp[ i ][j] 为前i个物品，ai的和为j的时候的最大总和。这么一来似乎我们就可以很简单的定义转移方程: dp[ i ][j] = max(dp[i-1][j], dp[i-1][j - a[i-1]]) 但是问题是这个必须大于等于0的限制怎么办呢？最开始我的想法是保证每个j都必须 >=0 以及 dp[ i ][j] - j (其实也就是 bi 的总和)必须 >=0。但是这么写出来发现不对！因为我们并不一定要求在每步转移的过程中 sum(ai) 都必须 >=0, 可能后面可以加上某　<ak, bk> 把sum(aj)加回正数。

既然这样，只好把这个限制条件去掉，也就是ｊ可以<0, 最后求 max(dp[n][j] | j >= 0 and dp[n][j] - j >= 0) 即可。这里有个隐藏的细节，是否有可能某数 x 是满足条件的最大值，但是不在dp里因为 dp[n][j] > x 同时 dp[n][j] - j < 0 呢? 答案是不可能。反证法：如果 dp[n][j] > x 同时 dp[n][j] - j < 0，又因为x满足条件因此凑足x的bi总和必然 >=0, 既然如此 j + sum(bi) 必然 > dp[n][j], 和条件矛盾。

想通这点，下面的问题是 j < 0 的话坐标怎么办，我们可以简单的把所有j都加上W=100000, 也就是 ai 总和的最大值。初始化的时候要注意，dp[0][W] = 0, 代表前0个物品一个都不取，其他 dp[0][X] = -INF. 代表不可能前0个物品凑足 sum(ai) = X。最后返回 dp[N][j]的最大值即可（但是必须满足条件 j >= 0 而且 dp[N][j] >= 0)

要点:
1. 当需要求满足一定条件限制下的最优化问题的时候可以考虑背包
2. 不一定什么时候都能空间优化到1维数组，特别是在dp[ i ][j]同时依赖于dp[i-1][j-xx]和dp[i-1][j+xx]的时候，但是滚动数组是什么时候都能用的！
3. 如果状态有负数可以考虑将其index加到正数,出于写起来方便的角度，可以写完code以后统一加。

我觉得如果是在美国找工作的话刷LC足够了，而且也非常有效。LC的优势除了题库针对性强和test case多以外，还有海量的大佬在讨论区解答。多看各路大佬的答案有种发现新世界的感觉，而书上的解答是不会更新和用到最新的库的。

黓龙君 发表于 2019-2-22 09:15
我觉得如果是在美国找工作的话刷LC足够了，而且也非常有效。LC的优势除了题库针对性强和test case多以外， ...

你说的很对哈哈，如果是出于找工作目的的话肯定还是赶紧刷 LC啊

charleszhou 发表于 2019-2-23 00:46
你说的很对哈哈，如果是出于找工作目的的话肯定还是赶紧刷 LC啊

我仔细看了下标题，原来楼主是要去挑战程序竞赛的大佬，膜拜！

马克一下，争取有空加入楼主

2.4 加工并且存储数据的数据结构

这一章的内容还都比较基础，简单总结一下。

2.4.1 树和二叉树

没有圈的连通图叫做树，没有圈的非连通图叫森林。一颗树的边数恰好是顶点数量-1。反之，边树等于顶点数-1的连通图就是一颗树。

二叉树是树中所有子节点都不超过２的树。

2.4.2 优先队列

也就是能够完成如下操作的数据结构:
    - 插入一个数值
　- 取出最小的数值，并且删除

优先队列用堆来实现。插入时首先把元素插在末尾，然后不断提升直到合适位置。删除时交换堆顶元素和最后一个元素，然后不断把堆顶元素下沉到合适位置，删除最后一个元素。操作复杂度均为 O(logN).堆用数组实现，实际操作用直接调用 priority_queue即可(注意C++默认最大堆，如果需要最小堆需要这么定义 priority_queue<int, vector<int>, greater<int> >).

2.4.3 二叉搜索树

可以高效进行如下操作:

  - 插入一个数值
  - 查询是否包含某个值
  - 删除某个值

以上复杂度均为O(logN).同样C++提供了set, map容器（和python定义不一样!)，都实现了平衡二叉树，可以直接拿来用。此外还有可以存放重复键值的multiset和multimap等容器。

2.4.4 并查集

这是用来管理元素分组情况的数据结构。可以高效进行如下操作：

  - 查询a和b是否属于同一组
  - 合并元素a和b所在的组

但是注意并查集无法进行分割操作。并查集用数组实现，具体来说初始化fa[ i ] = i, 表明每个节点都自成一组(其根节点等于自身)。合并则用fa[root_i] = root_j, 表示把i的根节点的父节点设置位j的根节点的父节点。查找两个节点是否在同一组只要检查这两个节点的根节点是否一致即可。注意两种常用的优化：

  - 路径压缩，也就是如果发现节点i的父节点不是根节点，则将i节点的父节点设置为其父节点的父节点（爷节点?)
  - rank 比较，rank设置为某一个根节点下子节点个数，初始化为0。我们永远把rank小的根节点并入rank大的根节点下面。

加了优化后并查集的合并查询操作非常之快，均摊复杂度优于 O(logN)。

例题：

POJ 2431: Expedition

一辆车初始距离重点为L, 油量为P, 起点到终点之间有N个加油站，每个加油站的位置以及油量都已经给出，问该车开到终点的最少加油次数。假设油量无限制。

思路：这题思路倒是比较直接。我们首先先贪心的往前开，开到不能开为止再回头考虑在哪里加油。显然我们应该选择在已经经历过的油量最多的加油站处加油。这样我们用一个pq来维护已经经历过的加油站的油量即可。如果开到不能开了然而pq是空的，显然就不能开到终点了。

POJ 3614: Sun screen

题意概括一下就是给C个interval的起始和结束位置, 以及L个点的位置和个数。如果点i处在某interval内，可认为该interval可以被该点消除（需要消耗一个点i的数量），问这Ｌ个点最多能消除多少 interval。

思路：这是一个想了很久想出来十分高兴然后再反思一下觉得不过如此的题目。假设我们按顺序考虑各个点，如果某点i既可以消灭interval A, 也能消除interval B, 那么应该选择用i来消除哪个interval呢？直觉是我们应该消除结束时间靠前的哪个interval,因为结束时间靠后的interval也许后面也有点可以将其消除。

想到这个之后我首先的想法是把所有interval按照结束时间排序，把点按照其位置排序，然后遍历所有点，找到该点能消除的所有interval。但是这样做的复杂度不幸是 O(LC)。想了很久，我突然意识到没必要从interval的角度来考虑 - 我们也可以把interval先按照开始时间排序。然后按顺序考虑所有点，然后把某点能cover到的interval都放到pq内，优先用该点消除结束时间更早的interval。这种做法的复杂度是 O(Llog(C))。

POJ 2010: Moo University - Financial Aid

给C个奶牛的成绩测试和所需要的奖学金 <score, fund>。假设现在需要录取N个奶牛，总能提供的奖学金为F,问所有录取方案中奶牛成绩中位数最大是多少。

思路：好题啊好题。这题我一看不就是背包么，可是这里要求的是最大中位数-如果改成最大成绩总和那自然就是用背包来求了。中位数怎么办呢？我们还是按照传统思路，如果输入是两个维度先按照其中一维排序。比如这里我们先按照score排序，然后开始考虑最大可能取到的中位数是多少？自然是 score[C-N/2-1]，至于能不能取到则取决于这个中位数左边和右边 N/2 个fund的最小值之和加上fund[C-N/2-1]是不是小于F。想到这里我们就可以把这题转化成 topK 来做了。

要点：
1. 输入是二维的时候先对一维排序真是屡试不爽。如果对原始顺序没有要求可以考虑
2. 不用考虑套路，模板，就从最基本的思路入手－如果是要手动brute force应该怎么做？往往在思考的时候正确的思路就会浮现
3. 一定一定要注意index的含义！比如这里我维护 topk[ i ],表示的是 0->i 个元素中的最小k个数之和，但是我用的时候却不知不觉把它当做了 0->i-1个元素中最小k个数之和。。然后伴随着的就是漫长的 debug。




补充内容 (2019-3-3 06:44):
优先队列的实现：
数组实现的完全二叉树。A[i]的左儿子节点坐标A[2*i+1], 右儿子A[2*i+2]。
heapify从 ceil[i/2] - 1 的节点挨个siftdown, 总复杂度O(N). 直觉：T(n) = 2*T(n/2) + O(logN)