算法竞赛入门经典（第二版）& 例题习题解答

这本书的编排思路很好，但过于言简意赅，不适合 C/C++ 入门，甚至有些劝退萌新，建议有人带着学习。

Chai 2016.12.25

读者须知

• 尊重知识产权，原书中的内容（如中文题面等）不会在这里给出，但不影响理解本博客给出的题解；
• 相较于原书中代码，本博客中的代码为现代 C++ 标准，更加追求 逻辑的清晰性 和 程序的可读性，不适合 C++ 零基础读者；
• 此页面列举的题目全部来自 AOAPC II: Beginning Algorithm Contests (Second Edition) (Rujia Liu)；
• UVa OJ 的创办者 Miguel Ángel Revilla 教授于 2018 年 2 月 14 日离世，目前由其子 Miguel Revilla Rodríguez 接手维护，由于 Valladolid 大学已经停止对 OJ 的资金支持，因此网站的链接去掉了 UVa 二级域名前缀，同时 Logo 也进行了更换。有能力的同学可以根据网站上的提示信息捐赠资金或者协助开发。

第 3 章 数组和字符串

• 例题 3-1 TeX 中的引号（TEX Quotes, UVa 272）
• 例题 3-2 WERTYU（WERTYU, UVa 10082）
• 例题 3-3 回文词（Palindromes, UVa 401）
• 例题 3-4 猜数字游戏的提示（Master-Mind Hints, UVa 340）
• 例题 3-5 生成元（Digit Generator, ACM/ICPC Seoul 2005, UVa 1583）
• 例题 3-6 环状序列（Circular Sequence, ACM/ICPC Seoul 2004, UVa 1584）
• 习题 3-1 得分（Score, ACM/ICPC Seoul 2005, UVa 1585）
• 习题 3-2 分子量（Molar Mass, ACM/ICPC Seoul 2007, UVa 1586）
• 习题 3-3 数数字（Digit Counting, ACM/ICPC Danang 2007, UVa 1225）
• 习题 3-4 周期串（Periodic Strings, UVa 455）
• 习题 3-5 谜题（Puzzle, ACM/ICPC World Finals 1993, UVa 227）
• 习题 3-6 纵横字谜的答案（Crossword Answers, ACM/ICPC Word Finals 1994, UVa232）
• 习题 3-7 DNA 序列（DNA Consensus String, ACM/ICPC Seoul 2006, UVa 1368）
• 习题 3-8 循环小数（Repeating Decimals, ACM/ICPC World Finals 1990, UVa 202）
• 习题 3-9 子序列（All in All, UVa 10340）
• 习题 3-10 盒子（Box, ACM/ICPC NEERC 2004, UVa 1587）
• 习题 3-11 换低档装置（Kickdown, ACM/ICPC NEERC, UVa 1588）
• 习题 3-12 浮点数（Floating-Point Numbers, UVa 11809）

第 4 章 函数和递归

• 例题 4-1 古老的密码（Ancient Cipher, NEERC 2004, UVa 1339）
• 例题 4-2 刽子手游戏（Hangman Judge, Hangman Judge, UVa 489）
• 例题 4-3 救济金发放（The Dole Queue, UVa 133）
• 例题 4-4 信息解码（Message Decoding, ACM/ICPC World Finals 1991, UVa 213）
• 例题 4-5 追踪电子表格中的单元格（Spreadsheet Tracking, ACM/ICPC World Finals 1996, UVa 512）
• 例题 4-6 师兄帮帮忙（A Typical Homework, UVa 12412）
• 习题 4-1 象棋（Xiangqi, ACM/ICPC Fuzhou 2011, UVa 1589）
• 习题 4-2 正方形（Squares, ACM/ICPC World Finals 1990, UVa 201）
• 习题 4-3 黑白棋（Othelllo, ACM/ICPC World Finals 1992, Uva 220）
• 习题 4-4 骰子涂色（Cube painting, UVa 253）
• 习题 4-5 IP 网络（IP Networks, ACM/ICPC NEERC 2005, UVa 1590）
• 习题 4-6 莫尔斯电码（Morse Mismatches, ACM/ICPC World Finals 1997, UVa 508）
• 习题 4-7 RAID 技术（RAID!, ACM/ICPC World Finals 1997, UVa509）
• 习题 4-8 特别困的学生（Extraordinarily Tired Students, ACM/ICPC Xi'an 2006, UVa 12108）
• 习题 4-9 数据挖掘（Data Mining, ACM/ICPC NEERC 2003, UVa 1591）
• 习题 4-10 洪水！（Flooded! ACM/ICPC World Finals 1999, UVa 815）

第 5 章 C++ 与 STL 入门

• 例题 5-1 大理石在哪儿？（Where is the Marble?, UVa 10474）
• 例题 5-2 木块问题（The Blocks Problem, UVa 101）
• 例题 5-3 安迪的第一个字典（Andy's First Dictionary, UVa 10815）
• 例题 5-4 反片语（Ananagrams, UVa 156）
• 例题 5-5 集合栈计算机（The SetStack Computer, ACM/ICPC NWERC 2006, UVa 12096）
• 例题 5-6 团体队列（Team Queue, UVa 540）
• 例题 5-7 丑数（Ugly Numbers, UVa 136）
• 例题 5-8 Unix ls 命令（Unix ls, UVa 400）
• 例题 5-9 数据库（Database, ACM/ICPC NEERC 2009, UVa 1592）
• 例题 5-10 PGA巡回赛的奖金（PGA Tour Prize Money, ACM/ICPC World Finals 1990, UVa 207） - 巨复杂的模拟，收益不大，直接跳过
• 例题 5-11 邮件传输代理的交互（The Letter Carrier's Rounds, ACM/ICPC World Finals 1999, UVa 814）
• 例题 5-12 城市正视图（Urban Elevations, ACM/ICPC World Finals 1992, UVa 221）
• 习题 5-1 代码对齐（Alignment of Code, ACM/ICPC NEERC 2010, UVa 1593）
• 习题 5-2 Ducci 序列（Ducci Sequence, ACM/ICPC Seoul 2009, UVa 1594）
• 习题 5-3 卡片游戏（Throwing cards away I, UVa 10935）
• 习题 5-4 交换学生（Foreign Exchange, UVa 10763）
• 习题 5-5 复合词（Compound Words, UVa 10391）
• 习题 5-6 对称轴（Symmetrym, ACM/ICPC Seoul 2004, UVa 1595）
• 习题 5-7 打印队列（Printer Queuek, ACM/ICPC NWERC 2006, UVa 12100）
• 习题 5-8 图书管理系统（Borrowers, ACM/ICPC World Finals 1994, UVa 230）

后面的基本上都是复杂的模拟题，做起来很繁琐，需要耐心，萌新可以考虑直接进入下一章的学习。

• 习题 5-9 找 Bug（Bug Hunt, ACM/ICPC Tokyo 2007, UVa 1596）
• 习题 5-10 在 Web 中搜索（Searching the Web, ACM/ICPC Beijin 2004, UVa 1597）
• 习题 5-11 更新字典（Updating a Dictionary, UVa 12504） - 此题不复杂，可做
• 习题 5-12 地图查询（Do You Know the Way to San Jose?, ACM/ICPC World Finals 1997, UVa 511）

稍微复杂的模拟题考察的更多的是工程能力，即写代码的素质，而非对数据结构和算法的掌握。但如果对一个题目能够想到用合适的数据结构进行模拟，整个流程也会简单很多，这需要经验积累，容易劝退。因此这里建议直接进入后面的专题练习，感受一下算法训练，有空回过头来挑战复杂的大模拟。

第 6 章 数据结构基础

读了一下，卧槽怎么还是在搞模拟题，根本不是入门书啊，暂时弃坑看别的了，以后回来再写。

原书相关信息

---

---