[题目] 《算法竞赛入门经典(第 2 版)》

sywgz 在 2014-05-23 创建 开放分组:全部用户 上次编辑时间:2018-09-19

本页面是《算法竞赛入门经典(第 2 版)》的题目索引。

第 1 部分 语言篇

前两章的习题貌似不在 UVa 上……

第 3 章 数组和字符串

3.1 数组

3.2 字符数组

3.3 竞赛题目选讲

3.4 注解与习题

第 4 章 函数和递归

4.1 自定义函数和结构体

4.2 函数调用与参数传递

4.3 递归

4.4 竞赛题目选讲

4.5 注解与习题

第 5 章 C++与 STL 入门

5.1 从 C 到 C++

5.2 STL 初步

5.3 应用:大整数类

5.4 竞赛题目举例

5.5 习题

第 2 部分 基础篇

第 6 章 数据结构基础

6.1 再谈栈和队列

例题 6-1 并行程序模拟(UVa 210 Concurrency Simulator)

例题 6-2 铁轨(UVa 514 Rails)

例题 6-3 矩阵链乘(UVa 442 Matrix Chain Multiplication)

6.2 链表

例题 6-4 破损的键盘(UVa 11988 Broken Keyboard)

例题 6-5 移动盒子(UVa 12657 Boxes in a Line)

6.3 树和二叉树

例题 6-6 小球下落(UVa 679 Dropping Balls)

例题 6-7 树的层次遍历(UVa 122 Trees on the level)

例题 6-8 (UVa 548 Tree)

例题 6-9 天平(UVa 839)

例题 6-10 下落的树叶(UVa 699 The Falling Leaves)

例题 6-11 四分树(UVa 297)

6.4 图

例题 6-12 油田(UVa 572 Oil Deposits)

例题 6-13 古代象形符号(UVa 1103)

例题 6-14 Abbott的复仇(UVa 816)

例题 6-15 给任务排序(UVa 10305)

例题 6-16 单词(UVa 10129)

黑白图像

走迷宫

拓扑排序

欧拉回路

 6.5 竞赛题目选讲

例题 6-17 看图写树(UVa 10562)

例题 6-18 雕塑(UVa 12171)

例题 6-19 自组合(UVa 1572)

例题 6-20 理想路径(UVa 1599)

例题 6-21 系统依赖 (UVa 506)

例题 6-22 战场(UVa 11853)

 6.6 训练参考

习题6-9 纸牌游戏(UVa 127)

木块问题(UVa 101) 「好像并没有这个题」

救济金发放(UVa 133) 「好像并没有这个题」

第 7 章 暴力求解法

7.1 简单枚举

例题 7-1 除法

例题 7-2 最大乘积

例题 7-3 分数拆分

7.1.4 双基回文数

7.2 枚举排列

7.2.1 生成1~n的排列

7.2.2 生成可重集的排列

7.2.3 解答树

7.2.4 下一个排列

7.3 子集生成

7.3.1 增量构造法

7.3.2 位向量法

7.3.3 二进制法

7.4 回溯法

7.4.1八皇后问题

7.4.2其他应用举例

 例题 7-4 素数环(UVa 524 Prime Ring Problem)(类似

 例题 7-5 困难的串(UVa 129 Krypton Factor)

 例题 7-6 带宽(UVa 140 Bandwidth)

 例题 7-7 天平难题(UVa 1354 Mobile Computing)

7.5 路径寻找问题

八数码问题

 例题 7-8 倒水问题(UVa 10603 Fill)

 例题 7-9 万圣节后的早晨(UVa 1601 The Morning afterbody Halloween)

7.6 迭代加深搜索

埃及分数问题

 例题 7-10 编辑书稿(UVa 11212 Editing a Book)

7.7 竞赛题目选讲

 例题 7-11 宝箱(UVa 12325 Zombie's Treasure Chest)

 例题 7-12 旋转游戏(UVa 1343 The Rotation Game)

 例题 7-13 快速幂计算(UVa 1374 Power Calculus)

 例题 7-14 网格动物(UVa 1602 Lattice Animals)

 例题 7-15 破坏正方形(UVa 1603 Square Destroyer)

7.8 训练参考

第 3 部分 竞赛篇

第 8 章 高效算法设计

8.1 算法分析初步

8.1.1 最大连续和

8.2 再谈排序与检索

8.2.1 逆序对问题 火柴排队 补:排序工作量·加强版

8.2.2 快速选择问题

8.3 递归与分治

8.2-1 棋盘覆盖问题

8.2-2 循环日程表问题

8.2-3 巨人与鬼

8.4 贪心法

8.4.1 背包相关问

8.4.1-1 最优装载问题

8.4.1-2 部分背包问题

8.4.1-3 乘船问题 

8.4.2 区间相关问题

8.4.2-1 选择不相交区间

8.4.2-2 区间选点问题 

8.4.2-3 区间覆盖问题

8.4.3 Huffman编码

8.4.3-1 最优编码问题

8.5 算法设计与优化策略

例题 8-1 煎饼

例题 8-2 联合国大楼 

例题 8-3 和为0的4个值

例题 8-4 传说中的车

例题 8-5 Gergoia的酒的交易

例题 8-6 两亲性分子

例题 8-7 唯一的雪花

例题 8-8 防线

例题 8-9 平均值 

8.6 竞赛题目选讲

 例题 8-10 抄书(UVa 714 Copying Books)

 例题 8-11 全部相加(UVa 10954 Add All)

 例题 8-12 奇怪的气球膨胀(UVa 12627 Erratic Expansion)

 例题 8-13 环形跑道(UVa 11093 Just Finish it up)

 例题 8-14 与非门电路(UVa 1607 Gates)

 例题 8-15 Shuffle 的播放记录(UVa 12174 Shuffle)

 例题 8-16 不无聊的序列(UVa 1608 Non-boring sequences)

 例题 8-17 不公平竞赛(UVa 1609 Foul Play)

 例题 8-18 洞穴(UVa1442 Cave)

 例题 8-19 贩卖土地(UVa 12265 Selling Land)

第 9 章 动态规划初步

9.1 数字三角形

例9.1.1 数字三角形

9.2 DAG 上的动态规划

9.2.1 DAG模型

经典问题 嵌套矩形 

经典问题 硬币问题

9.2.2 最长路及其字典序

9.2.3 固定终点的最长路和最短路

9.2.4 小结与应用举例 

例题 9-1 城市里的间谍(UVa 1607 A Spy in the Metro)

例题 9-2 巴比伦塔(UVa 437 The Tower of Babylon)

例题 9-3 旅行

例题 9-4 单向TSP(UVa 116 Unidirectional TSP)

9.3 多阶段决策问题(0-1 背包问题)

例题 9.3.2a 物品无限的背包问题

例题 9.3.2b 0-1 背包问题

例题 9-5 劲歌金曲

9.4 递归结构中的动态规划

例题 9.4.1a 最长上升子序列问题

例题 9.4.1b 最长公共子序列问题

例题 9-6 照明系统设计

例题 9-7 划分成回文串

例题 9-8 颜色的长度

例题 9.4.1c 最优矩阵链乘

例题 9.4.1d 最优三角剖分

例题 9-9 切木棍

例题 9-10 括号序列

例题 9-11 最大面积最小的三角剖分

例题 9.4.2a 树的最大独立集

例题 9.4.2b 树的重心

例题 9.4.2c 树的最长路径

例题 9-12 工人的请愿书

例题 9-13 Hali-Bula的晚会

例题 9-14 完美的服务

例题 9.4.3a 最优配对问题

例题 9.4.3b 货郎担问题

例题 9.4.3c 图的色数

例题 9-15 校长的烦恼

例题 9-16 20个问题

例题 9-17 基金管理

例题 9-18 跳舞机

例题 9-19 团队分组

例题 9-20 装满水的气球

例题 9-21 修缮长城

例题 9-22 越大越好

例题 9-23 有趣的游戏

例题 9-24 书架

例题 9-25 轻松爬山

例题 9-26 一个调度问题

例题 9-27 方块消除

例题 9-28 独占访问2

例题 9-29 整数传输

例题 9-30 给孩子起名

例题 9-31 送披萨

第 10 章 数学概念与方法

10.1 数论初步

例题 10-1 巨大的斐波那契数!(UVa 11582 Colossal Fibonacci Number)

例题 10-2 不爽的裁判(UVa 12169 Disgruntled Judge)

例题 10-3 选择与除法(UVa 10375 Choose and Divide)

例题 10-4 最小公倍数的最小和(UVa 10791 Minimum Sum LCM)

例题 10-5 GCD等于XOR (UVa 12716 GCD XOR)

10.2 计数与概率基础

例题 10-6 无关的元素(UVa 1635 Irrelevant Elements)

例题 10-7 交表(UVa 10820 Send a Table)

例题 10-8 密码(UVa 1262 Password)

例题 10-9 决斗(UVa 1636 Headshot)

例题 10-10 奶牛和轿车(UVa 10491 Cows and Cars)

例题 10-11 条件概率(UVa 11181 Probability Given)

例题 10-12 纸牌游戏(UVa 1637 Double Patience)

10.3 其他数学专题

10.3.1 递推

例题 10-13 危险的组合(UVa 580 Critical Mass)

例题 10-14 比赛名次(UVa 12034 Race)

例题 10-15 杆子的排列(UVa 1638 Pole Arrangement)

10.3.2 数学期望

例题 10-16 过河(UVa 12230 Crossing Rivers)

例题 10-17 糖果(UVa 1639 Candy)

例题 10-18 优惠券(UVa 10288 Coupons)

10.3.3 连续概率

例题 10-19 概率(UVa 11346 Probability)

例题 10-20 你想当 2^n 元富翁吗?(UVa 10900 So you want to be a 2^n-aire?)

例题 10-21 多边形(UVa 11971 Polygon)

10.4 竞赛题目选讲

例题 10-22 统计问题(UVa 1640 The Counting Problem)

例题 10-23 多少块土地(UVa 10213 How Many Pieces of Land?)

例题 10-24 ASCII面积(UVa 1641 ASCII Area)

例题 10-24 约瑟夫的数论问题(UVa 1363 Joseph's Problem)

例题 10-26 帮帮Tomisu(UVa 11440 Help Mr.Tomisu)

例题 10-27 树林里的树(UVa 10214 Trees in a Wood)

例题 10-28 高速公路 (UVa 1393 Highway)

例题 10-29 魔法GCD(UVa 1642 Magical GCD)

10.5 训练参考

习题 10-1 砌砖(UVa 11040 Add Bricks in the Wall)

习题 10-2 勤劳的蜜蜂(UVa 808 Bee Breeding)

习题 10-3 角度和正方形(UVa 1643 Angles and Squares)

习题 10-4 素数间隔(UVa 1644 Prime Gap)

习题 10-5 不同素数之和(UVa 1213 Sum of Different Primes)

第 11 章 图论模型与算法

11.1 再谈树

11.1.1 无根树转有根树

11.1.2 表达式树

例题 11-1 公共表达式消除(UVa 12219 Common Subexpression Elimination)

11.2 最小生成树

例题 11-2 苗条的生成树(UVa 1395 Slim Span)

例题 11-3 买还是建(UVa 1151 Buy or Build)

11.3 最短路问题

例题 11-4 电话圈(UVa 247 Calling Circles)

例题 11-5 噪音恐惧症(UVa 10048 Audiophobia)

例题 11-6 这不是Bug,而是特性(UVa 658 It's not a Bug, It's a Feature!)

11.4 网络流初步

例题 11-7 UNIX插头(UVa 753 a Plug for UNIX)

例题 11-8 矩阵解压(UVa 11082 Matrix Decompressing)

例题 11-9 海军上将(UVa 1658 Admiral)

例题 11-10 最优巴士路线设计(UVa 12264 Optimal Bus Route Design)

11.5 竞赛题目选讲

例题 11-11 有趣的赛车比赛(UVa 12661 Funny Car Racing)

例题 11-12 水塘(UVa 1515 Pool construction)

例题 11-13 混合图的欧拉回路(UVa 10735 Euler Circuit)

例题 11-14 星际游击队(UVa 1279 Asteroid Rangers)

例题 11-15 帮助小罗拉(UVa 1659 Help Little Laura)

第 12 章 高级专题

12.1 知识点选讲

12.1.1 自动机

例题 12-1 语言的历史(UVa 1671 History of Languages)

例题 12-2 不相交的正规表达式(UVa 1672 Disjoint Regular Expresssions)

例题 12-3 数字子串的和(UVa 1673 str2int)

12.1.2 树的经典问题和方法

例题 12-4 铁人比赛(UVa 12161 Ironman Race in Treeland)

例题 12-5 快乐涂色(UVa 11994 Happy Painting)

例题 12-6 闪电的能量(UVa 1674 Lightning Energy Report)

12.1.3 可持久化数据结构

例题 12-7 自带版本控制功能的IDE(UVa 12538 Version Controlled IDE)

12.1.4 多边形的布尔运算

例题 12-8 多边形相交(UVa 805 Polygon Intersections)

例题 12-9 王国 重新合并(UVa 1675 Kingdom Reunion)

例题 12-10 清洁机器人(UVa 12314 The Cleaning Robot)

12.2 难题选解

12.2.1 数据结构

例题 12-11 航班(UVa 1520 Flights)

例题 12-12 背单词(UVa 1676 GRE Words Revenge)

例题 12-13 瓦里奥世界(UVa 11998 Rujia Liu Loves Wario Land!)

12.2.2 网络流

例题 12-14 芯片难题(UVa 1104 Chips Challenge)

例题 12-15 《第七夜》、《时空轮回》与水的故事(UVa 12567 Never7,Ever17 and Water)

例题 12-16 怪兽滴水嘴(UVa 12110 Gargoyle)

12.2.3 数学

例题 12-17 简单加密法(UVa 12253 Simple Encryption)

例题 12-18 伟大的游戏——石头剪刀布(UVa 12164 The Great Game)

例题 12-19 自行车(UVa 1677 Cycling)

例题 12-20 折纸公理6(UVa 1678 Huzita Axiom 6)

例题 12-21 简单几何(UVa 1679 Easy Geometry)

12.2.4 几何

例题 12-22 打怪物(UVa 12162 Shooting the Monster)

例题 12-23 快乐的轮子(UVa 1017 Merrily,We Roll Along!)

例题 12-24 客房服务(UVa 1286 Room Services)

例题 12-25 最短飞行路径(UVa 1288 Shortest Flight Path)

12.2.5 非完美算法

例题 12-26 可爱的魔法曲线(UVa 12565 Lovely Magical Curves)

例题 12-27 奇怪的歌剧院(UVa 11188 A Strange Opera House)

例题 12-28 最小包围长方体(UVa 12308 Smallest Enclosing Box)

12.2.6 杂题选讲

例题 12-29 旅行(UVa 1680 Journey)

例题 12-30 下雨(UVa 1097 Rain)

例题 12-31 字典(UVa 1681 Dictionary)

例题 12-32 算符破译(UVa 11199 Equations in Disguise)

例题 12-33 独占访问(UVa 1682 Exclusive Access)

例题 12-34 压缩(UVa 11521 Compressor)

例题 12-35 公式编辑器(UVa 12417 Formula Editor)

例题 12-36 疯狂的谜题(UVa 12666 Killer Puzzle)

例题 12-37 太空站之迷(UVa 12731 Mysterious Space Station)

关于 《算法竞赛入门经典(第 2 版)》 的讨论
Gravatar
NVIDIA
积分:1929
提交:231 / 548
恩,复习好东西
空之轨迹Falcom






2015-10-15 19:31:07 1楼