算法競賽入門經典：習題與解答（簡體書）

《算法競賽入門經典——習題與解答》是在《算法競賽入門經典（第2 版）》的基礎上，延伸出來的一本習題與解答圖書，它把C 語言、算法和解題有機地結合在一起，淡化理論，注重學習方法和實踐技巧，是一本算法競賽的入門和提高教材。《算法競賽入門經典——習題與解答》分為5 章。 章是各種編程訓練技巧以及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年畢業于華北水利水電學院機械設計專業。曾就職于上海微軟全球技術支持中心，擔任.虛擬機(CLR)以及Visual Studio Extensibility技術咨詢顧問。2008年進入金融IT行業，就職于北京贊同信息技術有限公司，擔任高級技術經理，負責基于.平臺的銀行業務平臺開發。現就職于北京宇信科技集團股份有限公司，擔任高級產品經理，專注于移動互聯網、大數據和區塊鏈技術在銀行IT系統的應用和產品研發。多年來對算法研究一直充滿濃厚興趣，在工作之余堅持基礎算法的學習訓練，略有心得，2012年曾作為第二作者出版專著《算法競賽入門經典-訓練指南》。

數萬讀者翹首以盼！暢銷9年的算法好書《算法競賽入門經典》配套題解重磅推出！適合語言零基礎的初學者；算法競賽主要知識點的入門與拓寬；近200道競賽真題分析；實用主義的C 和STL講解；簡潔、清晰、高效的示例代碼。

章編程技巧與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-AtlanticUSA 344

ACM/ICPC North America - RockyMountain 345

ACM/ICPC North America - East CentralNA 347

ACM/ICPC North America - Mid-CentralUSA 363

ACM/ICPC Latin America 364

ACM/ICPC SWERC（SouthwesternEurope 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（大連賽區）后的謎題（TheLast 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