查看: 6219|回复: 8

ACM-ICPC参赛者人手一册讲解算法的书，你准备了没？

字体大小: 正常放大

0 主题	0 听众	0 积分

升级 0%

该用户从未签到

自我介绍: 技术圈里的非技术人

电梯直达

1^#

发表于 2013-7-18 09:37 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

本帖最后由 zuoninger 于 2013-7-18 09:39 编辑

世界顶级程序设计高手的经验总结 # P9 d: d% m* A' T7 |
【ACM-ICPC全球总冠军】巫泽俊主译
5 V# H4 s# s2 D. l7 a/ }日本ACM-ICPC参赛者人手一册

先来介绍一下我们这本应该人手一册的《挑战程序设计竞赛》（第2版）译者，这颗闪耀在编程竞赛中的明星巫泽俊，就在2011年的5月30下午2时，他获得了第35届ACM国际大学生程序设计竞赛全球总决赛冠军，媒体称他为“世界最聪明的人”。（见下图）

巫泽俊平时训练的实验室

巫泽俊

让我们看顶级ACM-ICPC总冠军是如何来介绍这本译作的!

程序设计竞赛因其涉及的知识面广，比赛形式激烈有趣，吸引了越来越多的学生参与其中。参赛者不但可以从中锻炼算法设计能力，还能够提高代码编写能力。其中的佼佼者也受到了越来越多国际知名公司的重视和欢迎。本书的几位作者是世界公认的顶尖选手，在竞赛和学术领域都取得了令人瞩目的成就。他们结合自己的专业知识和比赛经验，将自己的心得和技巧集结成书。

全书将不同的算法和例题按专题编排成小节，再将不同的小节由易到难分成四章，这样即便是初出茅庐的新手也不会有太大的阅读障碍。书中涵盖了在程序设计竞赛中会用到的大多数算法和技巧，并在附录中补充了书中未介绍但也比较有用的算法。在题材的安排上，作者取舍得当，主次分明，循序渐进，不以华而不实的奇技淫巧误导读者，又具有一定深度，相信即便是经验丰富的老将同样能从书中有所斩获。本书在结合例题进行讲解时，不是简单地堆砌问题和代码，而是注重引导读者更好地理解和运用算法来分析解决问题。对于正在学习数据结构与算法的读者而言，把它作为一本练习和拓展的参考书也是很好的选择。

本书在日本广受好评，还先后在台湾地区和韩国出版。近年来程序设计竞赛在亚洲发展很快，在中国大陆也出版了不少相关书籍，但鲜见高质量的佳作。所以，在读到此书时，我们非常惊喜，迫切希望中国大陆也能引进这样的好书。2012年初，我们通过作者的推特了解到了本书第二版的出版，一些前辈们踊跃翻译计算机专业书籍的经历也鼓舞了我们，让我们萌生了亲自翻译此书的念头并联系了图灵教育。非常幸运的是，图灵教育也正考虑引进此书，于是有了今天呈现在各位读者面前的简体中文版。

在翻译上，我们力求做到既尊重国内选手的习惯，又符合计算机专业的表述。在修正原书中的一些笔误的同时，加入了一些译者注，以方便国内读者理解。但由于译者水平有限，不足之处在所难免，还望读者多多包涵，并不吝提出意见和建议。

在翻译过程中，秋叶拓哉、岩田阳一和北川宜稔三位作者耐心地对我们的一些疑问和笔误给予了一一解答和确认。浙江大学的陈越、王灿和翁恺三位老师不但将我们领进了“快乐”竞赛的大门，还拨冗审阅了译稿并提出了宝贵的意见。网上不少同好也对本书的出版给予了关切和支持。在此谨对他们表示感谢。

从目录中了解这本书是否符合你的需求

第1章　蓄势待发——准备篇
1.1 　何谓程序设计竞赛
1.2 　最负盛名的程序设计竞赛
1.2.1 　世界规模的大赛——Google Code Jam（GCJ）
1.2.2 　向高排名看齐！——TopCoder
1.2.3 　历史最悠久的竞赛—— ACM-ICPC
1.2.4 　面向中学生的信息学奥林匹克竞赛——JOI-IOI
1.2.5 　通过网络自动评测——Online Judge（OJ）
1.3 　本书的使用方法
1.3.1 　本书所涉及的内容
1.3.2 　所用的编程语言
1.3.3 　题目描述的处理
1.3.4 　程序结构
1.3.5 　练习题
1.3.6 　读透本书后更上一层楼的练习方法
1.4 　如何提交解答
1.4.1 　POJ的提交方法
1.4.2 　GCJ的提交方法
1.5 　以高效的算法为目标
1.5.1 　什么是复杂度
1.5.2 　关于运行时间
1.6 　轻松热身
1.6.1 　先从简单题开始
1.6.2 　POJ的题目Ants
1.6.3 　难度增加的抽签问题
阅读
第2章　初出茅庐——初级篇
2.1 　最基础的“穷竭搜索”
2.1.1 　递归函数
2.1.2 　栈
2.1.3 　队列
2.1.4 　深度优先搜索
2.1.5 　宽度优先搜索
2.1.6 　特殊状态的枚举
2.1.7 　剪枝
2.2 　一往直前！贪心法
2.2.1 　硬币问题
2.2.2 　区间问题
2.2.3 　字典序最小问题
2.2.4 　其他例题
2.3 　记录结果再利用的“动态规划”
2.3.1 　记忆化搜索与动态规划
2.3.2 　进一步探讨递推关系
2.3.3 　有关计数问题的DP
2.4 　加工并存储数据的数据结构
2.4.1 　树和二叉树
2.4.2 　优先队列和堆
2.4.3 　二叉搜索树
2.4.4 　并查集
2.5 　它们其实都是“图”
2.5.1 　图是什么
2.5.2 　图的表示
2.5.3 　图的搜索
2.5.4 　最短路问题
2.5.5 　最小生成树
2.5.6 　应用问题
2.6 　数学问题的解题窍门
2.6.1 　辗转相除法
2.6.2 　有关素数的基础算法
2.6.3 　模运算
2.6.4 　快速幂运算
2.7 　一起来挑战GCJ的题目（1）
2.7.1 　Minimum Scalar Product
2.7.2 　Crazy Rows
2.7.3 　Bribe the Prisoners
2.7.4 　Millionaire
阅读
第3章　出类拔萃——中级篇
3.1 　不光是查找值！“二分搜索”
3.1.1 　从有序数组中查找某个值
3.1.2 　假定一个解并判断是否可行
3.1.3 　最大化最小值
3.1.4 　最大化平均值
3.2 　常用技巧精选（一）
3.2.1 　尺取法
3.2.2 　反转（开关问题）
3.2.3 　弹性碰撞
3.2.4 　折半枚举（双向搜索）
3.2.5 　坐标离散化
3.3 　活用各种数据结构
3.3.1 　线段树
3.3.2 　Binary Indexed Tree
3.3.3 　分桶法和平方分割
3.4 　熟练掌握动态规划
3.4.1 　状态压缩DP
3.4.2 　矩阵的幂
3.4.3 　利用数据结构高效求解
3.5 　借助水流解决问题的网络流
3.5.1 　最大流
3.5.2 　最小割
3.5.3 　二分图匹配
3.5.4 　一般图匹配
3.5.5 　匹配、边覆盖、独立集和顶点覆盖
3.5.6 　最小费用流
3.5.7 　应用问题
3.6 　与平面和空间打交道的计算几何
3.6.1 　计算几何基础
3.6.2 　极限情况
3.6.3 　平面扫描
3.6.4 　凸包
3.6.5 　数值积分
3.7 　一起来挑战GCJ的题目（2）
3.7.1 　Numbers
3.7.2 　No Cheating
3.7.3 　Stock Charts
3.7.4 　Watering Plants
3.7.5 　Number Sets
3.7.6 　Wi-fi Towers
第4章　登峰造极——高级篇
4.1 　更加复杂的数学问题
4.1.1 　矩阵
4.1.2 　模运算的世界
4.1.3 　计数
4.1.4 　具有对称性的计数
4.2 　找出游戏的必胜策略
4.2.1 　游戏与必胜策略
4.2.2 　Nim
4.2.3 　Grundy数
4.3 　成为图论大师之路
4.3.1 　强连通分量分解
4.3.2 　2-SAT
4.3.3 　LCA
4.4 　常用技巧精选（二）
4.4.1 　栈的运用
4.4.2 　双端队列的运用
4.4.3 　倍增法
4.5 　开动脑筋智慧搜索
4.5.1 　剪枝
4.5.2 　A*与IDA*
4.6 　划分、解决、合并：分治法
4.6.1 　数列上的分治法
4.6.2 　树上的分治法
4.6.3 　平面上的分治法
4.7 　华丽地处理字符串
4.7.1 　字符串上的动态规划算法
4.7.2 　字符串匹配
4.7.3 　后缀数组
4.8 　一起来挑战GCJ的题目（3）
4.8.1 　Mine Layer
4.8.2 　Year of More Code Jam
4.8.3 　Football Team
4.8.4 　Endless Knight
4.8.5 　The Year of Code Jam

稍后会上传迷你书！！！

zan

ACM-ICPC