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

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

第5章 基础题目选解

5.1 字符串

5.1.1   WERTYU UVa 10082 - WERTYU

例5.1.2   TEX括号 UVa 272 - TEX Quotes

5.1.3   周期串 UVa 455 - Periodic Strings

5.2 高精度

5.2.1   小学生算术 UVa 10035 - Primary Arithmetic

5.2.2   阶乘的精确值 UVa 623 - 500!

5.3 排序与检索

5.3.1   6174问题

5.3.2   字母重排 UVa 642 - Word Amalgamation

5.4 数学基础

5.4.1   Cantor的数表 UVa 264 - Count on Cantor

5.4.2   因子和阶乘 UVa 160 - Factors and Factorials

5.4.3   果园里的树 UVa 143 - Orchard Trees

5.5训练参考


第6章 数据结构基础

6.1 栈和队列

例题6-1   并行程序模拟UVa210

例题6-2   铁轨 UVa 514 - Rails

例题6-3   矩阵链乘UVa442

6.2 链表

例题6-4   破损的键盘(悲剧文本)UVa11988

例题6-5   移动盒子UVa12657

6.3 二叉树

例题6-6    小球下落UVa679

例题6-7    层次遍历 UVa122

例题6-8    树UVa548

例题6-9    天平UVa839

例题6-10  下落的树叶UVa699

例题6-11  四分树UVa297

6.4 图

例题6-12  油田 UVa572

例题6-13 古代象形符号 UVa1103

例题6-14  Abbott的复仇 UVa816

例题6-15  给任务排序 UVa10305

例题6-16  单词 UVa10129  

例6.4.1 黑白图像

例6.4.2 走迷宫

例6.4.3 拓扑排序

例6.4.4 欧拉回路

 6.5 竞赛题目选讲

例题6-17  看图写树 UVa10562

例题6-18  雕塑 UVa12171

例题6-19  自组合 UVa1572

例题6-20  理想路径UVa1599

例题6-21  系统依赖 UVa506

例题6-22   战场UVa11853

 6.6 训练参考

线性表

uva127    纸牌游戏 

uva101    木块问题  

uva133    救济金发放

二叉树

uva548    树求和

uva699    落叶

图与图的遍历

uva572    油田

第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 训练参考


第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 城市里的间谍

例题9-2 巴比伦塔

例题9-3 旅行

例题9-4 单向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-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)

第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,而是特性(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  简单几何(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
积分:1902
提交:231 / 548
恩,复习好东西
空之轨迹Falcom






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