算法竞赛入门经典：习题与解答

　　作者授课视频资料：https://space.bilibili.com/208090093

数万读者翘首以盼！
　　畅销9年的算法好书《算法竞赛入门经典》配套题解重磅推出！
　　适合语言零基础的初学者；
　　算法竞赛主要知识点的入门与拓宽；
　　近200道竞赛真题分析；
　　实用主义的C++和STL讲解；
　　简洁、清晰、高效的示例代码。

　　《算法竞赛入门经典——习题与解答》是在《算法竞赛入门经典（第2版）》的基础上，延伸出来的一本习题与解答图书，它把C++语言、算法和解题有机地结合在一起，淡化理论，注重学习方法和实践技巧，是一本算法竞赛的入门和提高教材。
　　《算法竞赛入门经典——习题与解答》分为5章。第1章是各种编程训练技巧以及C++11语法特性的简单介绍。第2章精选了一部分《算法竞赛入门经典（第2版）》的习题进行分析、解答。第3章是ACM/ICPC比赛真题分类选解，挑选了近些年ACM/ICPC比赛中较有价值的题目进行分析并解答。第4～5章是比赛真题选译，整理并翻译了近几年来各大区域比赛中笔者认为值得学习训练的比赛真题。
　　如果你对算法感兴趣，如果你是一名程序员或即将成为一名程序员，如果你想大幅提升自己的算法思维能力，如果你有志于参加ACM/ICPC、NOIP、NOI等竞赛，那就来吧！《算法竞赛入门经典——习题与解答》将为你推开一扇算法世界的大门！
　　法竞赛入门经典（第2版）》的习题进行分析、解答。第3章是ACM/ICPC比赛真题分类选解，挑选了近
　　些年ACM/ICPC比赛中较有价值的题目进行分析并解答。第4～5章是比赛真题选译，整理并翻译了近几
　　年来各大区域比赛中笔者认为值得学习训练的比赛真题。
　　如果你对算法感兴趣，如果你是一名程序员或即将成为一名程序员，如果你想大幅提升自己的算法思维能
　　力，如果你有志于参加ACM/ICPC、NOIP、NOI等竞赛，那就来吧！本书将为你推开一扇算法世界的大门！

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

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

　　前言
　　“请问《算法竞赛入门经典（第2版）》有没有配套题解啊？很多练习题好难，真希望能有一本简单、易懂的参考解答！”经常有读者追问类似的问题。笔者在进行训练学习时，也经常会有这样的想法。虽然很多题目可以在网上搜到对应题解，但这些题解多数是解题者为方便自己做题而随手记录的，解答过程未必严密、系统，语言表达上也比较随意，初学者理解起来就有一定的难度。
　　多年之前，笔者曾有幸参与了《算法竞赛入门经典—训练指南》一书的编写工作，收获颇大。也正是那次，我深刻感受到了自己在算法领域的不足，以及思维能力的亟待提升。私下里，我曾和刘汝佳老师商量，就以《算法竞赛入门经典（第2版）》的习题为训练题目，强迫自己在解出每道题之后，再对自己的思路进行严密、仔细的剖析，通过大量的训练，使自己得到一次系统的训练和提升。这次训练，使我记了厚厚一大本的笔记，而这本笔记就是本书的缘起。
　　希望本书能帮助更多跟我一样迫切需要提升算法思维能力的初学者！
　　算法有什么用
　　我大学学的是机械专业，但由于对数学非常热爱，加之毕业后发现软件行业貌似比较好“混”，且工资待遇比其他行业高些，所以就进入了开发领域。经过一段时间的工作后，我发现自己经常会遇到以下一些问题：
　　?程序稍微复杂一些，代码就会写的很乱。
　　?程序出了问题，不知道该如何调试，只会到处修改，然后再看效果。
　　?用户需求稍作改变，就想骂街。
　　?特别重要的一点是，如果你想跳到外企去工作，面试时肯定会让你编一些很难的算法程序。
　　后来，我进入到了微软上海全球技术支持中心做外包技术支持，接触到了许多严谨、求是、好学的工程师前辈。从他们身上，我学到了一些非常有效的解决问题的思路，以及那种“活到老学到老”的人生态度。
　　我逐渐明白：程序是要设计的。为了设计得清晰，需要学习数据结构、操作系统原理等非常多的基础知识，而这些体系本质上是前辈人思维方法的结晶。
　　另外，令很多程序员头疼的调试过程，给我印象最深的是一句话：调试的本质实际上就是在定位。大多数时候，调试的过程（并发程序的调试可能就更复杂些）其实就是一个二分查找：假如有100行程序结果不对，就可以在第50行看看结果是否符合预期，如果OK，说明问题出在后50行，否则前50行一定有问题。如此递归下去，很快就能精准定位到有问题的代码。了解二分查找的朋友都知道，这个算法复杂度是O(logn)。
　　用C#开发服务端程序时，我经常会遇到内存问题，需要对垃圾收集（GC）的过程进行分析调试。深入学习之后我发现，其实GC模型的本质就是有向图。抱着这个思路再来分析解决内存问题，思路瞬间清晰了很多。
　　这样的例子还有很多。
　　在不断解决各类问题的过程中，我逐渐明白了—算法在本质上是诸多计算机学术以及实践领域积累下来的分析解决各种问题的思维方法。它不是象牙塔内的纯学术研究，更不是一堆仅能用来解决特定领域性能问题的高精尖技术。这个行业的技术人员，本质上正是以这些思维方法为武器，高效解决着不同行业领域不断涌现出的各类纷繁问题和挑战。
　　说到这里，我想到其他很多行业：京剧艺人每天早上要练嗓子，相声演员每天要练贯口，军人在战斗之余要进行大量训练，中医在繁忙之余要天天钻研《伤寒论》《黄帝内经》等经典……类似这样，需要认真对待并把基本功训练作为生活一部分的行业还有很多。对于笔者来说，算法思维就是IT相关行业的技术人员需要用同样态度持续不断进行训练的一项基本功。
　　所以，就有了这些年的学习过程，以及以本书作为省察的一个小小总结。
　　内容安排
　　本书内容分为以下5章。
　　第1章是各种编程训练技巧以及C++11语法特性的简单介绍。
　　第2章精选了一部分《算法竞赛入门经典（第2版）》的习题进行分析、解答，主要是读者反映较多的第3~11章的课后习题部分。
　　第3章是ACM/ICPC比赛真题分类选解，挑选了近些年ACM/ICPC比赛中较有价值的题目进行分析并解答。
　　第4章是比赛真题选译，整理并翻译了近几年来各大区域比赛中笔者认为值得学习训练的比赛真题。
　　第5章是比赛难题选译，内容类似于第4章，只是题目难度更上一个台阶。
　　关于C++语言的使用
　　本书在解答各类算法题目时，使用C++作为主要的编程语言，尽量使用STL中提供的现成数据结构，同时也尽量使用C++11的新特性。因为笔者认为，算法训练最关键的是训练解决问题的思维能力，包括抽象能力、分析能力、调试能力等，应该充分利用语言提供的语法特性使得程序更加简洁清晰，从而使解题者更专注于问题的抽象和分析本身。
　　关于题目代码
　　本书中的所有题目，笔者都是先完成代码并在线提交AC（Accepted），然后才开始编写对应的分析题解。有些需要附上代码的题目，笔者会尽可能把代码的主要部分（去掉模板代码以及C++的namespace导入部分）附在题目后面，但由于篇幅原因，实在无法全部放入书中。还有些题目，虽然已经在线提交AC，但由于无法严格证明题目的正确性，也没有在书中提供题解。
　　书中的所有代码，读者朋友们如有需要，可以通过如下网站进行下载：https://github.com/sukhoeing/aoapc-bac2nd-keys。
　　勘误和支持
　　虽然笔者已竭尽全力，力求减少纰漏，但由于水平有限，书中难免仍存在错漏之处，恳请广大读者朋友们批评指正。欢迎您将学习过程中遇到的各类问题、您对本书的想法以及宝贵意见，通过本书网站的issues部分一起交流。
　　致谢
　　首先要感谢刘汝佳老师，是他把我带进了算法艺术的大门，并且在工作极其繁忙的情况下一直耐心地指导着我的算法学习。
　　从小父亲就告诉我，对的事情一定要坚持。这句话支撑着我渡过了很多艰难的日子。同时，也要感谢我的太太梁明珠和女儿陈婉之。这三年来，我牺牲了大量本该陪伴他们的时间，投入到了本书的创作中。没有你们的支持和包容，我不可能完成这本书。
　　还要感谢微软工作期间经常指导我的老师张羿，从他那里，我第一次知道了世界上还有ACM/ICPC这回事。在如何做好一个程序员这件事上，他给了我非常多有价值的指导和帮助。
　　本书初稿完成之后，许多同学和朋友踊跃参与到了本书的试读中，并且提出了许多有价值的意见和反馈，他们的名字（排名不分先后）是陈飞、崔晨、杨恒杰、林永康、陈坤泽、孙博昊等。另外，书中的部分题目也参考了许多网友的在线题解，在此一并表示感谢。
　　最后要感谢清华大学出版社的贾小红编辑，用极大的耐心容忍着我把交稿时间一拖再拖，希望本书不会让您失望。
　　陈锋