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

《算法竞赛入门经典——习题与解答》是在《算法竞赛入门经典（第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)以及Visual Studio Extensibility技术咨询顾问。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.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.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.3 C 与 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/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（达卡）           423

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