errata.md

[TOC]

算法竞赛入门经典 - 勘误

第 7 章 暴力求解法

• TODO: 例题7-1 分析里面说枚举量降低到不到1万，这个不对，应该说枚举量的数量级降低到一万。做一下实验发现，枚举量最大的时候是n=2，示例代码中fghij从1234枚举到50000

第 8 章高效算法设计

• TODO: 例题8-12 g(k,I)=2g(...)+c(k),应为g(k,I)=2g(...)+c(k-1)
• TODO: 紫书例题8-17，uva 1609，foul play。题目说1队可以战胜半数以上的队，那黑队应该不超过一半。但图8-25里面一共24个队，黑队占了14个，该图是否有误？另外，我想能不能每轮都让黑队互相火并，让1队跟它能打赢的队比赛，这样也可以让1队夺冠啊。不知道我是否题目理解有误，请指教。
• TODO: 紫书例题8-18，P250， "先求出左延伸...的最大值h1(i)，再求往右延伸...的最大值h2(i)..." 应为 "先求出右延伸...的最大值h1(i)，再求往左延伸...的最大值h2(i)..." 因为题目后来提到h1(i)的计算是从左往右扫描。

第 9 章动态规划初步

• TODO: 紫书p293页例题9-22 最后一行例如n=6，m=3时，解应为111（而非书上的666)

第 10 章数学概念与方法

• TODO: 例题10-1 如何证明可以在n^2范围内再次出现f0和f1？已知f0=0，f1=1 猜想反例：是否会有一种情况使得从fx，fx+1处到fy，fy+1处产生循环节，满足fx!=f0，如果出现这种情况，由于fy，fy+1的值可以唯一确定后面的序列，则fi(i<x)的序列将不再出现重复，后面的序列一直保持fx到fy的循环

第 11 章图论模型与算法

• TODO: 习题11-10标错了题号, 且翻译不清，没有说明每个士兵只能移动一次。

算法竞赛入门经典(第2版)：习题与解答 - 勘误

2.1 第 3 章 数组和字符串

• 习题3-3 C[n+1][k]=C[n][k]+x,其中x应该是k在n+1中出现的次数，而不是n。

2.2 第 4 章 函数和递归

2.3 第 5 章 C++与 STL 入门

2.4 第 6 章 数据结构基础

2.5 第 7 章 暴力求解法

2.6 第 8 章高效算法设计

2.7 第 9 章动态规划初步

2.8 第 10 章数学概念与方法

2.9 第 11 章图论模型与算法

• 习题11-11 因为调用了sort函数使时间复杂度变为了O(NlogN)而非书上的O(N)，另外书上沿用了刘汝佳紫书习题11-11的翻译，感觉这个翻译非常模糊，没有说明权值和容量的相关性。
• 习题11-12 绿书p230习题11-12中也有显然的sort造成的log因子，时间复杂度上不应忽略，应为O(nm*α(nm)*log(nm)+T)

2.10 第 12 章高级专题

• 习题12-1 自编SketchUp p243 程序结束后多了个一样的main函数

习题选解 第 3 章 比赛真题分类选解