挑战程序设计竞赛.pdf

所需积分/C币:50 2016-06-01 15:12:04 5.74MB PDF
10
收藏 收藏
举报

本书的作者们参加过众多程序设计竞赛,在平时的练习和学习中,也获得了各种各样的知识与技 巧,本书将这些知识技巧总结成册,主要介绍算法及其在相关问题中的应用。本书依照由易及难 的顺序对问题进行讲解,章节的编排也参考了主题的难易程度及其相互的联系,内容较多的主题 则按难易程度划分为多个子主题分别介绍。各个主题由算法介绍和例题讲解穿插而成。
最负盛名的程序设计竞赛 ★ Google Code Jam(GCJ) google公司举办的一年一度的程序设计竞赛。 影响力最大、参赛面最广的程序设计竞赛 ●每道题都有Sma和 Large等不同规模的测试数据。 自由选择喜欢的工具在本地运行程序,并提交结果。 ★ Top Coder Top Coder公司举办的程序设计竞赛。既有周期举办 的SRM,又有一年一度的TCO。 ●在75分钟内挑战难度和分数递增的三道题 ●每道题的得分随用时递减 ●独有的挑战阶段,通过寻找他人程序的漏洞赚取额 外的分数。 系统评测的结果在最后才公布。 ★ACM-|CPC 美国计算机协会(ACM)主办的面向大学生的竞赛。 ●历史最悠久、最负盛名的程序设计竞赛。 ●三名选手共用一台电脑的团体比赛。 ●5个小时内挑战10道左右的问题。 译者序 程序设计竞赛因其涉及的知识面广,比赛形式激烈有趣,吸引了越来越多的学生参与其中。参赛 者不但可以从中锻炼算法设计能力,还能够提高代码编写能力。其中的佼佼者也受到了越来越多 国际知名公司的重视和欢迎。 本书的几位作者是世界公认的顶尖选手,在竞赛和学术领域都取得了令人瞩目的成就。他们结合 自己的专业知识和比赛经验,将自己的心得和技巧集结成书 全书将不同的算法和例题按专题编排成小节,再将不同的小节由易到难分成四章,这样即便是初 出茅庐的新手也不会有太大的阅读障碍。书中涵盖了在程序设计竞赛中会用到的大多数算法和技 巧,并在附录中补充了书中未介绍但也比较有用的算法。在题材的安排上,作者取舍得当,主次 分明,循序渐进,不以华而不实的奇技淫巧误导读者,又具有一定深度,相信即便是经验丰富的 老将同样能从书中有所斩获。本书在结合例题进行讲解时,不是简单地堆砌问题和代码,而是注 重引导读者更好地理解和运用算法来分析解决问题。对于正在学习数据结构与算法的读者而言, 把它作为一本练习和拓展的参考书也是很好的选择。 本书在日本广受好评,还先后在台湾地区和韩国出版。近年来程序设计竞赛在亚洲发展很快,在 中国大陆也岀版了不少相关书籍,但鲜见高质量的佳作。所以,在读到此书时,我们非常惊喜, 迫切希望中国大陆也能引进这样的好书。2012年初,我们通过作者的推特了解到了本书第二版的 出版,一些前辈们踊跃翻译计算机专业书籍的经历也鼓舞了我们,让我们萌生了亲自翻译此书的 念头并联系了图灵教育。非常幸运的是,图灵教育也正考虑引进此书,于是有了今天呈现在各位 读者面前的简体中文版。 在翻译上,我们力求做到既尊重国内选手的习惯,又符合计算机专业的表述。在修正原书中的- 些笔误的同时,加入了一些译者注,以方便国内读者理解。但由于译者水平有限,不足之处在所 难免,还望读者多多包涵,并不吝提出意见和建议。 2译者序 在翻译过程中,秋叶拓哉、岩田阳一和北川宜稔三位作者耐心地对我们的一些疑问和笔误给予了 一一解答和确认。浙江大学的陈越、王灿和翁恺三位老师不但将我们领进了“快乐”竞赛的大门, 还拨冗审阅了译稿并提岀了宝贵的意见。网上不少同好也对本书的出版给予了关切和支持。在此 谨对他们表示感谢。 巫泽俊庄俊元李津羽 2013年5月6日于浙江大学 前言 如今,形形色色的程序设计竞赛层出不穷,听说过 Google Code Jam、 Top Coder、 ACM-ICPO的读 者恐怕不在少数。本书要介绍的正是这类以在规定时间内、又快又准地解决尽可能多的题目为目 标的程序设计竞赛 程序设计竞赛内涵丰富,即便是经验老道的程序员,要想在比赛中取得好成绩也绝非易事。要在 程序设计竞赛中取胜,不仅需要运用灵活的想象和丰富的知识得岀正确的算法,还需要一气呵成 地实现并调试通过。 另一方面,程序设计竞赛对新手而言亦非遥不可及。为了让更多的参赛选手体会到比赛的乐趣, 大多数比赛都会准备若干面向初学者的题目。另外,即便未能在比赛中取得好成绩,通过比赛 也能够使自己的能力得到有效的锻炼。最重要的是,大家能够享受到激烈的比赛带来的乐趣。 本书的作者们参加过众多程序设计竞赛,在平时的练习和学习中,也获得了各种各样的知识与技 巧,本书将这些知识技巧总结成册,主要介绍算法及其在相关问题中的应用。本书依照由易及难 的顺序对问题进行讲解,章节的编排也参考了主题的难易程度及其相互的联系,内容较多的主题 则按难易程度划分为多个子主题分别介绍。各个主题由算法介绍和例题讲解穿插而成。 只要是具有编程基础知识的读者,均适合阅读本书。书中的源代码均用C++实现,不过只用到了 其基本功能,所以即便读者不熟悉C+也不影响阅读。 关于再版】 令人惊喜的是,本书的第1版受到了广大读者的高度评价,在此表示感谢。特别是一些并不热衷 于程序设计竞赛的读者也购买了本书。这是因为通过本书不仅可以学到算法,更能学到其设计和 运用的思想。这正是本书划时代的亮点。 本书第2版追加了计算几何、搜索减枝、分治法和字符串相关算法4个主题。此外还追加了方便读者 加深理解的练习题,并为学有余力的读者列出了书中未涉及的拓展主题,进一步丰富了本书内容。 目录 第1章蓄势待发——准备篇………11.6.1先从简单题开始 …16 1.1何谓程序设计竞赛 1.6.2POJ的题目Ants… 18 1.2最负盛名的程序设计竞赛……………5 1.6.3难度增加的抽签问题· 0 1.2.1世界规模的大赛 第2章初出茅庐——初级篇 Google Code Jam (GCJ) 1.2.2向高排名看齐! 2.1最基础的“穷竭搜索” …………26 TopCoder………5 2.1.1递归函数 26 1.2.3历史最悠久的竞赛 2.1.2栈 27 ACM-ICPC…… 2.1.3队列 24面向中学生的信息学奧林匹克 2.1.4深度优先搜索………29 竞赛—JOI-IOI 1.5宽度优先搜索 1.2.5通过网络自动评测 2.1.6特殊状态的枚举 7 Online Judge (OJ) 2.1.7剪枝 38 1.3本书的使用方法 2.2一往直前!贪心法………………39 3.1本书所涉及的内容 2.2.1硬币问题 1.3.2所用的编程语言 2.2.2区间问题 1.3.3题目描述的处理 223字典序最小问题 …43 1.3.4程序结构………………………7 224其他例题 45 1.3.5练习题 23记录结果再利用的“动态规划”……51 1.3.6读透本书后更上一层楼的练习 2.3.1记忆化搜索与动态规划… 51 方法 8 2.3.2进一步探讨递推关系 1.4如何提交解答 233有关计数问题的DP 1.4.1POJ的提交方法…9 2.4加工并存储数据的数据结构……………70 1.4.2GCJ的提交方法 2.4.1树和二叉树 ……………70 5以高效的算法为目标 2.4.2优先队列和堆…………………71 1.5.1什么是复杂度 15 2.4.3二又搜索树 1.5.2关于运行时间 …15 2.44并查集………………84 1.6轻松热身… 2.5它们其实都是“图” 目 录 25.1图是什么 3.4.3利用数据结构高效求解……206 2.5.2图的表示 3.5借助水流解决问题的网络流 209 2.5.3图的搜索 97 3.5.1最大流 2.5.4最短路问题 352最小割… 212 2.5.5最小生成树… 3.5.3二分图匹配 217 2.5.6应用问题 107 3.54一般图匹配 0 2.6数学问题的解题窍门……………11 3.55匹配、边覆盖、独立集和顶点 辗转相除法………… 覆盖 2.6.2有关素数的基础算法 117 3.5.6最小费用流…………………………22 2.6.3模运算 121 3.57应用问题 228 2.6.4快速幂运算 122 3.6与平面和空间打交道的计算几何 27一起来挑战GCJ的题目(1) 3.6.1计算几何基础……………250 2.7.1 Minimum scalar product…………125 3.6.2极限情况…………………………255 2.7.2 Crazy rows…………127 36.3平面扫描 ………258 2.7.3 Bribe the Prisoners 129 3.6.4凸包 260 2.7.4 Millionaire 132 36.5数值积分 263 3.7一起来挑战GCJ的题目(2)………267 第3章出类拔萃——中级篇……137 3.7.1 Numbers……………………………267 3.1不光是查找值!“二分搜索”………138 3.72 No Cheating………………269 3.1.1从有序数组中查找某个值……138 3.7.3 Stock Charts 3.1.2假定一个解并判断是否可行……140 3.7.4 Watering Plants 273 3.1.3最大化最小值… 3.7.5 Number sets………………278 3.1.4最大化平均值 3.7.6Wi- fi Towers…………………………280 3.2常用技巧精选(一) 146 3.2.1尺取法… ………146 第4章登峰造极——高级篇 …285 3.22反转(开关问题) …………150 41更加复杂的数学问题……………286 3.23弹性碰撞…… 158 4.1.1矩阵……286 .2.4折半枚举(双向搜索) 160 4.1.2模运算的世界 291 3.2.5坐标离散化 164 4.1.3计数 95 3.3活用各种数据结构……………………167 4.1.4具有对称性的计数 3.3.1线段树…… …167 4.2找出游戏的必胜策略 305 3.3.2 Binary Indexed Tree 4.2.1游戏与必胜策略 305 3.3.3分桶法和平方分割… 4.2.2Nim 34熟练掌握动态规划 191 4.2.3 Grundy数 315 3.4.1状态压缩DP …191 4.3成为图论大师之路…………………320 3.4.2矩阵的幂…………………199 4.3.1强连通分量分解……320 录3 4.3.22-SAT 324 4.7.1字符串上的动态规划算法……368 4.3.3LCA 328 4.7.2字符串匹配 4.4常用技巧精选(二) 335 4.7.3后缀数组 378 4.4.1栈的运用… 335 4.8一起来挑战GCJ的题目(3)……387 4.4.2双端队列的运用 4.8.1 Mine Layer 387 4.4.3倍增法 …345 4.8.2 Year of more code jan……………392 4.5开动脑筋智慧搜索……350 4.8.3 Football tean………………………395 4.5.1剪枝 350 4.8.4 Endless Knight. .....................399 4.5.2A*与IDA*…………………356 4.8.5 The Year of code jam…………403 4.6划分、解决、合并:分治法 359 4.6.1数列上的分治法 …359 本书中未涉及的拓展主题…408 4.6.2树上的分治法 360书中例题列表 4.6.3平面上的分治法… 参考文献 ··:····:·····:····:*······· 4.7华丽地处理字符串 368 第1章 蓄势待发——准备篇

...展开详情
试读 89P 挑战程序设计竞赛.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
挑战程序设计竞赛.pdf 50积分/C币 立即下载
1/89
挑战程序设计竞赛.pdf第1页
挑战程序设计竞赛.pdf第2页
挑战程序设计竞赛.pdf第3页
挑战程序设计竞赛.pdf第4页
挑战程序设计竞赛.pdf第5页
挑战程序设计竞赛.pdf第6页
挑战程序设计竞赛.pdf第7页
挑战程序设计竞赛.pdf第8页
挑战程序设计竞赛.pdf第9页
挑战程序设计竞赛.pdf第10页
挑战程序设计竞赛.pdf第11页
挑战程序设计竞赛.pdf第12页
挑战程序设计竞赛.pdf第13页
挑战程序设计竞赛.pdf第14页
挑战程序设计竞赛.pdf第15页
挑战程序设计竞赛.pdf第16页
挑战程序设计竞赛.pdf第17页
挑战程序设计竞赛.pdf第18页

试读结束, 可继续读2页

50积分/C币 立即下载 >