刘汝佳的《算法竞赛入门经典》该怎么学?

关注
刘汝佳的《算法竞赛入门经典》该怎么学?www.shan-machinery.com

我司书架

当时还在学OI的时候,kkk在考前遇到了这本书(当时还是第一版,称为蓝书),里面内容还没有紫书这么全,但是里面多样的例题、惊奇的思路令我大开眼界。虽然多数题目都没有真的去写完,但或多或少还是开拓了思维。它的确是一本好书。

然而,现在重新阅读这本书,发现它并不适合作为一般人(尤其是中小学生)的第一本算法竞赛的教材。它并不够入门,学习曲线陡峭,而且篇幅并不是非常详略得当。

对于这些读者来说,读这本书的感受:

首先,语言是最开始的部分。是的,它的确把算法竞赛需要的C++所需要的语言知识都过掉一遍了,也说了很多语言的提示;但是所选择的例题几乎就已经是简单的算法题,对于尚不能熟练掌握语言的初学者来说,还是过于复杂。

这个可以很明显的体现在篇幅中。紫书在去除STL部分后的语言不到100页,而“臭名昭著”的《一本通》也有近200页,《课课通》甚至有300页。当然篇幅并不能说明内容多少,比如《课课通》存在的大量的代码段和样例占了很多篇幅。不过根据群里读者的反应,就是——看懂了吗?看懂了!做这个题?这怎么用啊……

实际上《入门经典》在语言部分的知识信息量是很大的,但是浓缩在短短的100页中,对于举一反三能力稍弱的选手来说,的确不是那么容易理解。在我的学生中,有这样体会的人不是少数。

其次,有些部分过于倾向建模。例如,在图的一章,第一个例题就是用DFS求连通块。直到本章最后,都没有讲到“图”本身——顶点、边、权,没有讲如何建图(当然在非常后面的《图论模型与算法》一章还是提到了)。整章与其说是图,不如说是基础搜索(DFS和BFS)。

说到DFS,本书第一次出现这个术语应该是在《二叉树递归遍历》中出现。 这里,作者只简单的提到了前序根左右,中序左根右,后序左右根。我不认为一个只大概只知道函数遍历的读者可以很自然的理解这几句抽象话。实际上,到这边读者并没有详细介绍DFS。然后,在后面的章节,作者默认读者已经掌握了DFS程序的递归写法,这就造成了本来会的就会了,本来不会的还是一脸懵逼

作者将很多基本功的东西一句话带过,实际上这些内容并没有这么简单。我不否认有些神仙在第一次学习相关知识阅读本书的时候自带悟性,可以理解这些内容;但是根据调查,多数人还是觉得办不到。换句话说……基本功套路并没有详细介绍。当然你也可以认为读者应当“自行在互联网搜索资料学习”,但是这个不是一本“入门书”应当体现的姿态。

再者,有些重要的话题,本书不涉及,而是写进了《训练指南》。然而这样的编排会导致大幅增加读者的“主观能动性”的要求(更何况有很多读者认为《训练指南》是习题集,所以就没买),需要自己安排学习顺序——如果有人带还好,自学的话,如果没有正确的先后顺序,很容易劝退。

我认为的理想的教程难度应该是从前往后看,缓步上坡,不会遇到很大的阻力。但是《入门经典》并不是理想的自学难度的编排(左)。我认为理想的难度编排应该是右图。

因此,拿这本书作为算法竞赛的启蒙自学教程,应当

你有相当好的数理抽象理解能力;或者,有高人指导自学顺序,并且可以解答疑问。需要在配套题库进行大量的练习

虽然以上说了很多编排的问题,但是它依然是一本不可多得的好的算法参考书。如果你已经掌握了一些基础(语言、基础算法套路和数据结构,并能够完成一些基础模板题),那么读这本书会很大的收获。一方面本书语言严谨准确,没有什么错误;另一方面,里面的许多“提示”的确是竞赛选手需要注意的经验之谈,只是这些提示如果没有一些经验的积累,是不能深刻体会出来的(有点矛盾不是吗?但的确有这种感觉)。

无比认同作者的“知识不是看来的,而是刷题刷来的”。如果需要刷题,除了可以去配套的UvaOJ,还可以借用洛谷的RemoteJudge去评测这些题目(部分带有翻译,需要先绑定UvaOJ账号),体验会好一些,提升刷题效率。

题目列表 - 洛谷​www.luogu.com.cn

也提供题解,如果卡住可以学习

当然,以上仅为一家之言。如果你觉得自己可以,就从前往后读下去然后写题咯。毕竟小马过河,自己怎么样还是自己最清楚。

(Update on 2020.11.02)

其实,对于入门算法竞赛更合适的书籍,可以看看洛谷编写的《深入浅出程序设计竞赛 - 基础篇》,目前已经出版并可以买到。凭借这本书入坑算法竞赛应该不算难。

如何评价《深入浅出程序设计竞赛 - 基础篇》?​www.zhihu.com图标

https://www.shan-machinery.com