算法竞赛入门经典

刘汝佳

出版时间

2009-11-01

ISBN

9787302206088

评分

★★★★★

标签

算法

书籍介绍
这本书在读者口中反复被称作“最好的算法竞赛入门书”,但真正让它脱颖而出的,并非系统的知识罗列,而是那种把高深算法“讲人话”的能力。它用C/C++把语言、算法与解题拧成一股绳:讲动态规划时强调“核心是状态和状态转移方程,本身是一种思维手段”而非死记算法;讲字符串处理时提醒“本质是数组,不能用运算符直接赋值”这类新手必踩的坑。正因如此,它被广泛推荐为NOIP、ACM的入门与复赛教材。不过也有读者直言“习题太简单”“只是‘黑书’拆出来的”,这恰是它的定位取舍——适合刚踏入竞赛、想建立整体认知的初学者,而非寻求难题挑战者。它更像一位耐心的领路人,帮你把ACM从神坛上请下来。
作者简介
刘汝佳,1982年12月生,高中毕业于重庆市外国语学校。 2000年3月获得NOI2000全国青少年信息学奥林匹克竞赛一等奖第四名,进入国家集训队,并因此保送到清华大学计算机科学与技术系。大一时获2001年ACM/ICPC国际大学生程序设计竞赛亚洲一上海赛区冠军和2002年世界总决赛银牌(世界第四),2005年获学士学位,2008年获硕士学位。 学生时代曾为中国计算机学会NOI科学委员会学生委员,担任IOI2002-2008中国国家队教练,并为NOI系列比赛命题十余道。现为NOI竞赛委员会委员,并在NOI 25周年时获得中国计算机学会颁发的“特别贡献奖”。 2004年至今共为ACM/ICPC亚洲赛区命题二十余道,担任6次裁判和2次命题总监,并应邀参加IOI和ACM/lCPC相关国际研讨会,发表论文两篇。 2004年初作为第一作者出版专著《算法艺术与信息学竞赛》,2009年出版译著《编程挑战》。 多年来在全国二十余个城市进行中学生竞赛培训工作,为北京、上海、吉隆坡等地的著名高校授课与宣讲,并多次与TopCodet、百度和网易有道等知名企业合作举办比赛,让更多的IT人才获得展示自我的平台。
AI导读
核心看点
  • 结合C/C++语言与算法,淡化理论,注重解题技巧。
  • 覆盖暴力求解、动态规划、图论等竞赛核心知识点。
  • 提供大量实用编程、调试及测试技巧,代码规范易懂。
读者共识
  • 被公认为算法竞赛入门经典,讲解清晰且平易近人。
  • 习题难度适中,但部分读者认为过于简单或偏向高中。
  • 作者刘汝佳的另一力作,难度略低于其著名的黑书。
精彩摘录
  • "现在讨论最坏情况下也是O(n)的方案,把所有的数分为5个一堆,那么总共会有n/5堆,对于每堆我们可以很快的找到中位数(因为只有5个所以很容易嘛),之后调用当前算法找到这n/5个中位数的中位数,用这个数来做pivot,所以这个算法被叫做Median of Medians algorithm。 把中位数的中位数作为pivot的话,那么原数组中便会有3/5*1/2个也就是3/10个小于等于这个pivot的,同理会有3/10大于这个pivot的,所以最坏情况下,数组被分为30%,70%或者70%,30%的两部分。 T(n)<=T(n/5)+T(7/10*n)+O(n)<=c*n*(1+9/10+(9/"
  • "有趣的是,如果把状态定义成“d(i)表示以节点i为终点的最长路径长度”,也能顺利求出最优值,却难以打印出字典序最小的方案。想一想,为什么?你能总结出一些规律吗?"
  • "C语言中的字符型用关键字char表示,实际储存的是字符的ASCII码。字符常量可以用单引号法表示。在语法上可以当做int型使用。"
  • "可以用sprintf把格式化信息输出到字符串,保证buffer足够大。 由于字符串的本质是数组,只能用strcpy,strcmp,strcat来执行“赋值”,“比较”,“连接”操作。不能用=,==,<=,+等运算符。它们在string.h中。"
  • "使用fgetc可以从打开的文件读取一个字符。一般情况下应当检查不是EOF后再将其转换成char值。getchar等价于fgetc(stdin)。 fgets会读取完整的一行。就是说,它一旦读取到‘\n’,就会停止读取工作,然后在buffer后加‘\0’结束符。 头文件ctype.h中定义的isalpha,isdigit,isprint,等可以判断字符的属性,toupper,tolower等用来转换大小写。"
  • "字符还可以直接用ASCII码来表示。如果用八进制\o,十六进制就是\xh(h为16进制数字串)"
  • "为了方便使用,往往用typedef struct {域定义;}类型名;的方式定义一个新类型名。这样,就可以像原生数据类型一样使用这个自定义类型了。"
  • "建议用来判断某事物是否具有某种特殊性质的函数命名成“is_xxx”的形式。返回非0数为真,0为假。"
目录
第1部分 语言篇
第1章 程序设计入门 1
1.1 算术表达式 1
1.2 变量及其输入 3
1.3 顺序结构程序设计 6

显示全部
用户评论
前部分难度不大 后半部分难度提升极快~!
刘汝佳的又一部力作,难度稍弱于他的黑宝书
入门的好书啊,里面UVAOJ的题目大家有条件好好做一下啊
还是想看看,呵呵
电子版也有
入 门 经 典(不过内容实在有点少)
@2019-03-04 10:08:10
第一篇精读,第二篇略读,第三篇没读。等B站听完基础课程再回来研究二三篇进阶。
lrjnb
刚入ACM时候看这东西脑子要炸
下载
收藏