醉染图书算法竞赛入门经典9787302476580

1章 编程技巧与C++11语法特介绍 1
1.1编程技巧 1
1.1.1 排序能问题 1
1.1.2 整数输入 3
1.1.3 循环宏定义 3
1.1.4 STL容器内容调试输出 3
1.1.5 二维几何运算类 4
1.1.6 内存池 5
1.1.7 泛型参数的使用 5
1.1.8 位运算操作封装 6
1.1.9 编译脚本 7
1.2 C++11语言特介绍 7
1.2.1 类型推导（auto） 8
1.2.2 空指针值（nullptr） 8
1.. 容器的 for循环遍历 8
1.2.4 匿名函数（Lambda） 9
1.2.5 统一的初始化语法 10
1.2.6 哈希容器 11
第 2 章 《算法竞赛入门经典（第 2版）》习题选解 13
2.1数组和字符串 13
2.2函数和递归 26
. C++与 STL入门 37
2.4数据结构基础 76
2.5暴力求解法 108
2.6高效算法设计 139
2.7动态规划初步 166
2.8数学概念与方法 190
2.9图论模型与算法 214
2.10专题 
第 3 章 比赛真题分类选解 248
3.1搜索 248
3.2模拟 257
3.3动态规划 319
3.4组合递推 324
3.5图论 331
3.6正则表达式 333
第 4 章 比赛真题选译 341
ACM/ICPC North America - Greater NY 341
ACM/ICPC Africa/Middle East - Arab 342
ACM/ICPC North America - Mid-Atlantic USA 344
ACM/ICPC North America - Rocky Mountain 345
ACM/ICPC North America - East Central NA 347
ACM/ICPC North America - Mid-Central USA 363
ACM/ICPC Latin America 364
ACM/ICPC SWERC（Southwestern Europe Regionals） 367
ACM/ICPC Europe - Central 372
ACM/ICPC Europe - Northwestern 372
ACM/ICPC South Pacific 373
ACM/ICPC Asia – Tokyo（东京赛区） 373
ACM/ICPC Asia – Aizu（爱知赛区） 375
ACM/ICPC Asia – Fukuoka（福冈赛区） .375
ACM/ICPC Asia – Tehran（德黑兰） 376
ACM/ICPC Asia – Daejeon（韩国大田） 378
ACM/ICPC Asia – Harbin（哈尔滨赛区） 381
ACM/ICPC Asia – Changchun（长春赛区） 381
ACM/ICPC Asia – Shenyang（沈阳赛区） 382
ACM/ICPC Asia – Dalian（大连赛区）谜题（The Last Puzzle, Asia - Dalian 2011, LA5695） 386
ACM/ICPC Asia – Tianjin（天津赛区） 388
ACM/ICPC Asia – Changsha（长沙赛区） 389
ACM/ICPC Asia – Nanjing（南京赛区） 389
ACM/ICPC Asia – Guangzhou（广州赛区） 391
ACM/ICPC Asia – Shanghai（上海赛区） 392
ACM/ICPC Asia – Chengdu（成都赛区） 393
ACM/ICPC Asia – Hangzhou（杭州赛区） 396
ACM/ICPC Asia – Jinhua（金华赛区） 396
ACM/ICPC Asia – Taichung（台中赛区） 398
ACM/ICPC Asia – Kaohsiung（高雄赛区） 398
ACM/ICPC Asia – Amritapuri（印度 Amritapuri） 400
ACM/ICPC Asia – Hatyai（泰国合艾） 405
ACM/ICPC Asia – Bangkok（泰国曼谷） 407
ACM/ICPC Asia – Phuket（普吉岛赛区） 409
ACM/ICPC World Finals 410
CCPC（中国大学生程序设计竞赛） 412
第 5 章 比赛难题选译 415
ACM/ICPC Europe – Central 415
ACM/ICPC Europe – Northeastern 416
ACM/ICPC Asia – Taichung（台中） 420
ACM/ICPC Asia – Daejeon 422
ACM/ICPC Asia – Shanghai（上海） 422
ACM/ICPC Asia – Dhaka（达卡） 4
ACM/ICPC Asia – Mudanjiang（牡丹江） 424
ACM/ICPC Asia – Tehran（德黑兰） 427
ACM/ICPC Asia – Xian（西安） 427
ACM/ICPC Asia – Anshan 427
ACM/ICPC Asia – Beijing（北京） 429
ACM/ICPC Asia – Guangzhou（广州） 431
ACM/ICPC Asia – Tokyo（东京） 432
ACM/ICPC Asia – Bangkok（曼谷） 433

陈锋，1982年9月生，2004年于华北水利水电学院机械设计专业。
曾就职于上海微软优选技术支持中心，担任.net虚拟机(CLR)以及Visual Studio Extensibility技术咨询顾问。2008年进入金融IT行业，就职于北京赞同信息技术有限公司，担任不错技术经理，负责基于.net平台的银行业务平台开发。现就职于北京宇信科技集团股份有限公司，担任不错产品经理，专注于移动互联网、大数据和区块链技术在银行IT系统的应用和产品研发。
多年来对算法研究一直充满浓厚兴趣，在工作之余坚持基础算法的学习训练，略有心得，2012年曾作为第二作者出版专著《算法竞赛入门经典-训练指南》。

前 言
“请问《算法竞赛入门经典（第2版）》有没有配套题解啊？很多练习题好难，真希望能有一本简单、易懂的参考解答！”经常有读者追问类似的问题。笔者在进行训练学习时，也经常会有这样的想法。虽然很多题目可以在网上搜到对应题解，但这些题解多数是解题者为方便自己做题而随手记录的，解答过程未必严密、系统，语言表达上也比较随意，初学者理解起来就有一定的难度。
多年之前，笔者曾有幸参与了《算法竞赛入门经典—训练指南》一书的编写工作，收获颇大。也正是那次，我深刻感受到了自己在算法领域的不足，以及思维能力的亟待提升。私下里，我曾和刘汝佳老师商量，就以《算法竞赛入门经典（第2版）》的习题为训练题目，强迫自己在解出每道题之后，再对自己的思路进行严密、仔细的剖析，通过大量的训练，使自己得到一次系统的训练和提升。这次训练，使我记了厚厚一大本的笔记，而这本笔记就是本书的缘起。
希望本书能帮更多跟我一样迫切需要提升算法思维能力的初学者！
算法有什么用
我大学学的是机械专业，但由于对数学很热爱，加之后发现软件行业貌似比较好“混”，且工资待遇比行业高些，所以就进入了开发领域。经过一段时间的工作后，我发现自己经常会遇到以下一些问题：
? 程序稍微复杂一些，代码就会写的很乱。
? 程序出了问题，不知道该如何调试，只会到处修改，然后再看效果。
? 用户需求稍作改变，就想骂街。
? 特别重要的一点是，如果你想跳到外企去工作，面试时肯定会让你编一些很难的算法程序。

后来，我进入到了微软上海技术支持中心做外包技术支持，接触到了许多严谨、求是、好学的前辈。从他们身上，我学到了一些很有效的解决问题的思路，以及那种“活到老学到老”的人生态度。
我逐渐明白：程序是要设计的。为了设计得清晰，需要学习数据结构、操作系统原理等许多的基础知识，而这些体系本质上是前辈人思维方法的结晶。
另外，令很多程序员头疼的调试过程，给我印象很深的是一句话：调试的本质实际上就是在定位。大多数时候，调试的过程（并发程序的调试可能就更复杂些）其实就是一个二分查找：如有 100行程序结果不对，就可以在第50行看看结果符合预期，如果OK，说明问题出在后50行，否则前50行一定有问题。如此递归下去，很快就能精准定位到有问题的代码。了解二分查找的朋友都知道，这个算法复杂度是O(logn)。

用C#开发服务端程序时，我经常会遇到内存问题，需要对垃圾收集（GC）的过程进行分析调试。深入学习之后我发现，其实GC模型的本质就是有向图。抱着这个思路再来分析解决内存问题，思路瞬间清晰了很多。
这样的例子还有很多。
在不断解决各类问题的过程中，我逐渐明白了—算法在本质上是诸多计算机学术以及实践领域积累下来的分析解决各种问题的思维方法。它不是象牙塔内的纯学术研究，更不是一堆仅能用来解决特定领域能问题的高精尖技术。这个行业的技术人员，本质上正是以这些思维方法为武器，高效解决着不同行业领域不断涌现出的各类纷繁问题和挑战。
说到这里，我想到很多行业：京剧艺人每天早上要练嗓子，相声演员每天要练贯口，军人在战斗之余要进行大量训练，中医在繁忙之余要天天钻研《伤寒论》《黄帝内经》等经典……类似这样，需要认真对待并把基本功训练作为生活一部分的行业还有很多。对于笔者来说，算法思维就是IT相关行业的技术人员需要用同样态度持续不断进行训练的一项基本功。
所以，就有了这些年的学习过程，以及以本书作为省察的一个小小总结。
内容安排
本书内容分为以下5章。
1章是各种编程训练技巧以及C++11语法特的简单介绍。
第2章精选了一部分《算法竞赛入门经典（第2版）》的习题进行分析、解答，主要是读者反映较多的3~1章的课后习题部分。
第3章是ACM/ICPC比赛真题分类选解，挑选了近些年ACM/ICPC比赛中较有价值的题目进行分析并解答。
第4章是比赛真题选译，整理并翻译了近几年来各大区域比赛中笔者认为值得学习训练的比赛真题。
第5章是比赛难题选译，内容类似于第4章，只是题目难度更上一个台阶。
关于C++语言的使用
本书在解答各类算法题目时，使用C++作为主要的编程语言，尽量使用STL的成数据结构，同时也尽量使用C++11的新特。因为笔者认为，算法训练很关键的是训练解决问题的思维能力，包括抽象能力、分析能力、调试能力等，应该充分利用语言提供的语法特使得程序更加简洁清晰，从而使解题者更专注于问题的抽象和分析本身。
关于题目代码
本书中的所有题目，笔者都是先完成代码并在线提交AC（Accepted），然后才开始编写对应的分析题解。有些需要附上代码的题目，笔者会尽可能把代码的主要部分（去掉模板代码以及C++的namespace导入部分）附在题目后面，但由于篇幅原因，实在无法全部放入书中。还有些题目，虽然已经在线提交AC，但由于无法严格明题目的正确，也没有在书提题解。

书中的所有代码，读者朋友们如有需要，可以通过如下进行下载：https://itu.com/sukhoeing/aoapc-bac2nd-keys。
勘误和支持
虽然笔者已竭尽全力，力求减少纰漏，但由于水平有限，书中难免仍存在错漏之处，恳请广大读者朋友们批评指正。欢迎您将学习过程中遇到的各类问题、您对本书的想法以及宝贵意见，通过本书的issues部分一起交流。
致谢
首先要感谢刘汝佳老师，是他把我带进了算艺的大门，并且在工作极其繁忙的情况下一直耐心地指导着我的算法学习。
从小父亲就告诉我，对的事情一定要坚持。这句话支撑着我渡过了很多艰难的日子。同时，也要感谢我的太太梁明珠和女儿陈婉之。这三年来，我牺牲了大量本该陪伴他们的时间，投入到了本书的创作中。没有你们的支持和包容，我不可能完成这本书。
还要感谢微软工作期间经常指导我的老师张羿，从他那里，我知道了世界上还有ACM/ICPC这回事。在如何做好一个程序员这件事上，他给了我许多有价值的指导和帮。
本书初稿完成之后，许多同学和朋友踊跃参与到了本书的试读中，并且提出了许多有价值的意见和反馈，他们的名字（排名不分先后）是陈飞、崔晨、杨恒杰、林、陈坤泽、孙博昊等。另外，书中的部分题目也参考了许多网友的在线题解，在此一并表示感谢。
然后要感谢清华大学出版社的贾小红编辑，用极大的耐心容忍着我把交稿时间一拖再拖，希望本书不会让您失望。


陈锋

数万读者翘首以盼！

9年的算法好书《算法竞赛入门经典》配套题解！

适合语言零基础的初学者；

算法竞赛主要知识点的入门与拓宽；

近200道竞赛真题分析；

实用主义的C++和STL讲解；

简洁、清晰、高效的示例代码。