转载

笔记：《挑战程序设计竞赛（第2版）》（1）

笔记：《挑战程序设计竞赛（第2版）》

遥想一年半前买的这本书，结果拖延了一个学期才看，收获很大，不过有很多地方看不懂。最近开始准备蓝桥杯（是啊，比赛不到一个星期了……），又把这本书拿出来看。

首先感觉自己之前白看了……不过后来又慢慢还能回想起来一些，又一次收获很大。

也有比较开心的，一年前的很多完全看不懂的地方现在居然看得行云流水。应该要归功于自己理论背景的加深吧——自动机、组合数学、高数。

隔上一段时间回望自己，发现原来当时的自己那么嫩。而今天能有所察觉，算是有进步吧。

不过还是有一些地方要花时间去想，把它们记下来。

Page 16 : 三角形-注脚①

本题还有 O(nlogn) 时间更高效的算法，留给有兴趣的读者思考。

（1）先对n根棍子按长度排序，得到序列L

（2）从L中取最长的三根

如果能组成三角形则输出，结束
否则删除最长那根，转（2）

这里如果最长和两根次长不能组成三角形，则最长那根无论如何都不能跟其它棒子组成三角形了，所以删掉。

Page 47 : Fence Repair

作者直接给出来了要用Huffman树，没有解释原因。

我自己思考了一下（午），也算是给出个解释。

观察题目，从树的角度考虑，将切割过程看成一棵树，根是原始木板，一刀下去以后得出两个小木板就是它的两个子节点，再切子节点……

最后的叶节点就是最终所要求的木板( L1...Ln )。

将各节点所代表的 木板的长度 作为 节点的权 。

题目所求的开销就是 非叶子节点 的 权值之和 。

观察非叶子节点的组成，会发现其实每一个叶子节点在其每一个祖先节点上占有其权值。

也就是说， 权值之和 等于

sum( weight(Li) * depth(Li) ) (1 <= i <= n)

最短的板与次短的板的节点应当是兄弟节点

为什么？

其中 depth(Li) 是Li所在深度，以 depth(root) 为0。

如果我们将 depth(Li) 看成编码长度，而 weight(Li) 看成字母权重，就可以理解这里为什么要用Huffman树了。

那么新的问题是，我忘了Huffman树的证明了，不过现在时间紧急，留待以后去查吧。

Page 57 : 最长公共子序列问题的注脚①

如果稍微思考一下就能发现 s[i + 1] = t[j + 1] 时，只需令 dp[i + 1][j + 1] = dp[i][j] + 1 就可以了。

我思考了一下（午）。

用反证法，设：

dp[i + 1][j] - dp[i][j] >= 2

根据转移方程（Page 57顶），我们可以替换 dp[i + 1][j] ，有：

dp[i][j - 1] - dp[i][j] >= 1        （与定义不符）

或

dp[i][j] - dp[i][j] >= 2            （与定义不符）

或

dp[i + 1][j - 1] - dp[i][j] >= 2

对于这种情况，我不知道如何直接表示其不行，不过可以继续拆解它，有：

dp[i][j - 2] - dp[i][j] >= 1        （与定义不符）

或

dp[i][j - 1] - dp[i][j] >= 2        （与定义不符）

或

dp[i + 1][j - 2] - dp[i][j] >= 2

可以归纳，这样一直持续下去，可得

dp[i + 1][0] - dp[i][j] >= 2        （与定义不符）

即必有

dp[i + 1][j] - dp[i][j] < 2

同理，有

dp[i][j + 1] - dp[i][j] < 2

Page 68 : 多重集合数

这个题，因为公式比较复杂（对我来说），我的感觉是看公式不如看代码清晰。

其实题目的思想比较简单，首先可以简单理解 O(nm^2) 的算法，然后观察递推关系，发现计算 dp[i + 1] 中的每个值得计算都是用 dp[i] 的一个固定长度的窗口的累和，所以用滑动窗口思想降低复杂度。剩下比较麻烦的是一些边界条件处理。

Page 88 : 食物链

这个题比较抽象，难到我了，不过经过不懈的努力，还是理解了。

对我来说，题目最大的思维难点是为何要用三个元素表示一只动物。

这个想通了非常简单，枚举。

题目中所遭遇的困难是在处理过程中没有办法给予任意元素一个确定的值。

设想在处理过程中，一般地，我们有若干个集合。

相同集合的元素之间都有关系，不同集合中的元素都没有关系。

此时如果要对所有元素确定性赋值，元素只要满足其所在集合的要求就行了，其他集合对这个元素没有要求。

但在处理过程中会发生集合合并：合并有确定赋值的集合A，B，有A中元素a，原先B对a不做要求，但是现在要要求a取特定值，如果原先A对a的赋值不满足，则现在要跟据a重算A中所有元素的赋值以适应B。这一过程很复杂。

所以需要不确定的赋值，也就是枚举所有可能性。再看刚才的情形，某种确定的B对A中的a有确定的要求，只要将对应的a赋值与此种B关联就好了。

Page 113 : 线段上格点的个数

为何是最大公约数？（虽然给了个图解释，不过我还是没有直接领悟。）

给定一条两端点都在整数坐标上的斜线，有其在x轴上的投影长度为a，在y轴上的投影长度为b，a与b必为整数。

题目所求，即是最大的c，使得

a = da * c b = db * c

成立。da，db为整数。

这也就是求a，b的最大公约数啦。

Page 119 : 埃氏筛法

受到下一小节（区间筛法）的启发，这里有一些细节。

// 摘自书中Page 119 int primes[MAX_N]; bool is_prime[MAX_N + 1]; int sieve(int n) {  int p = 0;  for (int i = 0; i < n; i++) is_prime[i] = true;  is_prime[0] = is_prime[1] = false;  for (int i = 2; i <= n; i++) {   if (is_prime[i]) {    prime[p++] = i;    for (int j = 2 * i; j <= n; j += i)     is_prime[j] = false;   }  }  return p; }

注意到对于某个i和任意k(k < i)。

合法范围内的 k * i 必然已经被筛过了。因为k本身是素数或k的某个素因子。

所以对于内层循环j完全可以由 i * i 开始。

同时，可以发现，对于枚举倍数的目的，i的上限可以是 sqrt(n) 。此时， (sqrt(n), n] 范围内的素数已被筛出。（这一范围内的合数必然有一个小于等于 sqrt(n) 的质因子。

正文到此结束