Programming challenges:the programming contest training manual

目录
译者序
前言
第1章 入门
1.1 初识自动评测系统
1.1.1 评测系统反馈
1.2 挑选你的武器
1.2.1 程序设计语言
1.2.2 如何阅读本书的程序
1.2.3 标准输入输出
1.3 编程提示
1.4 基本数据类型
1.5 关于习题
1.6 习题
1.6.1 3n+1问题(3n+1 Problem)
1.6.2 扫雷(Minesweeper)
1.6.3 旅行(The Trip)
1.6.4 液晶显示屏(LC-Display)
1.6.5 图形化编辑器(Graphical Editor)
1.6.6 解释器(Interpreter)
1.6.7 将军(Check the Check)
1.6.8 澳大利亚投票(Australian Voting)
1.7 提示
1.8 注解
第2章 数据结构
2.1 基本数据结构
2.1.1 栈
2.1.2 队列
2.1.3 字典
2.1.4 优先队列
2.1.5 集合
2.2 库函数
2.2.1 C++标准模板库
2.3 程序设计实例:纸牌大战
2.4 准备行动
2.5 字符串输入输出
2.6 赢得战争
2.7 测试与调试
2.8 习题
2.8.1 快乐的跳跃者(Jolly Jumper)
2.8.2 扑克牌型(Poker Hands)
2.8.3 罢工(Hartals)
2.8.4 解密(Crypt Kicker)
2.8.5 完美洗牌术(Stack'em Up)
2.8.6 Erd?s数(Erd?s Numbers)
2.8.7 比赛记分板(Contest Scoreboard)
2.8.8 Yahtzee游戏(Yahtzee)
2.9 习题
2.10 注解
第3章 字符串
3.1 字符编码
3.2 字符串的表示
3.3 程序设计实例:公司更名
3.4 模式查找
3.5 字符串操作
3.6 程序的完成
3.7 字符串库函数
3.8 习题
3.8.1 WERTYU键盘(WERTYU)
3.8.2 寻找单词(Where's Waldorf?)
3.8.3 公共排列(Common Permutation)
3.8.4 解密II(Crypt Kicker II)
3.8.5 自动评测脚本(Automated Judge Script)
3.8.6 文件碎片(File Fragmentation)
3.8.7 Doublet序列(Doublets)
3.8.8 Fmt程序(Fmt)
3.9 提示
3.10 注解
第4章 排序
4.1 排序的应用
4.2 排序算法
4.3 程序设计举例:给绅士排名
4.4 与排序相关的库函数
4.5 给绅士排名
4.6 习题
4.6.1 Vito家族(Vito's Family)
4.6.2 煎饼堆(Stacks of Flapjacks)
4.6.3 过桥(Bridge)
4.6.4 最长打盹时间(Longest Nap)
4.6.5 鞋匠的烦恼(Shoemaker's Problem)
4.6.6 CDVII高速公路(CDVII)
4.6.7 龟壳排序(ShellSort)
4.6.8 足球(Football (aka Soccer))
4.7 提示
4.8 注解
第5章 算术与代数
5.1 机器算术
5.1.1 整数库函数
5.2 高精度整数
5.3 高精度算术
5.4 进制及其转换
5.5 实数
5.5.1 如何处理实数
5.5.2 分数
5.5.3 十进制实数
5.6 代数
5.6.1 多项式运算
5.6.2 多项式求根
5.7 对数
5.8 实数函数库
5.9 习题
5.9.1 小学生算术(Primary Arithmetic)
5.9.2 反转相加(Reverse and Add)
5.9.3 考古学家的烦恼(The Archeologist's Dilemma)
5.9.4 仅由1组成的数(Ones)
5.9.5 乘法游戏(A Multiplication Game)
5.9.6 多项式的系数(Polynomial Coefficients)
5.9.7 Stern-Brocot代数系统(The Stern-Brocot Number System)
5.9.8 两两之和(Pairsumonious Numbers)
5.10 提示
5.11 注解
第6章 组合数学
6.1 基本计数技巧
6.2 递推关系
6.3 二项式系数
6.4 其他计数序列
6.5 递归与数学归纳法
6.6 习题
6.6.1 斐波那契计数(How Many Fibs?)
6.6.2 土地分割(How Many Pieces of Land?)
6.6.3 数数(Counting)
6.6.4 括号表达式(Expressions)
6.6.5 完全树标号(Complete Tree Labeling)
6.6.6 牧师数学家(The Priest Mathematician)
6.6.7 自描述序列(Self-describing Sequence)
6.6.8 数轴行走(Steps)
6.7 提示
6.8 注解
第7章 数论
7.1 素数
7.1.1 寻找素数
7.1.2 素数的个数
7.2 整除性
7.2.1 最大公约数
7.2.2 最小公倍数
7.3 模算术
7.4 同余
7.4.1 同余运算
7.4.2 求解线性同余式
7.4.3 不定方程
7.5 数论函数库
7.6 习题
7.6.1 开灯与关灯(Light, More Light)
7.6.2 Carmichael数(Carmichael Numbers)
7.6.3 欧几里德问题(Euclid Problem)
7.6.4 阶乘与整除(Factovisors)
7.6.5 四素数之和(Summation of Four Primes)
7.6.6 Smith数(Smith Numbers)
7.6.7 弹珠(Marbles)
7.6.8 重新打包(Repackaging)
7.7 提示
7.8 注解
第8章 回溯法
8.1 回溯法
8.2 构造所有子集
8.3 构造所有排列
8.4 程序设计举例:八皇后问题
8.5 搜索中的剪枝
8.6 习题
8.6.1 棋盘上的象(Little Bishops)
8.6.2 15数码游戏(15-Puzzle Problem)
8.6.3 队伍(Queue)
8.6.4 服务站(Servicing Stations)
8.6.5 拔河(Tug of War)
8.6.6 伊甸园(Garden of Eden)
8.6.7 色彩缤纷游戏(Color Hash)
8.6.8 拼接正方形(Bigger Square Please...)
8.7 提示
8.8 注解
第9章 图遍历
9.1 图的不同属性
9.2 图的数据结构
9.3 图的遍历:宽度优先
9.3.1 宽度优先遍历
9.3.2 遍历的应用
9.3.3 寻找路径
9.4 图的遍历:深度优先
9.4.1 寻找环
9.4.2 连通分量
9.5 拓扑排序
9.6 习题
9.6.1 双着色(Bicoloring)
9.6.2 摆弄轮子(Playing With Wheels)
9.6.3 导游(The Tourist Guide)
9.6.4 斜线迷宫(Slash Maze)
9.6.5 递变阶梯(Edit Step Ladders)
9.6.6 立方体之塔(Tower of Cubes)
9.6.7 从黄昏到拂晓(From Dusk till Dawn)
9.6.8 汉诺塔卷土重来!(Hanoi Tower Troubles Again!)
9.7 提示
第10章 图算法
10.1 图论
10.1.1 度的性质
10.1.2 连通性
10.1.3 图中的回路
10.1.4 平面图
10.2 最小生成树
10.3 最短路
10.3.1 Dijkstra算法
10.3.2 每对结点之间的最短路
10.4 网络流和二分图匹配
10.5 习题
10.5.1 斑点(Freckles)
10.5.2 项链(The Necklace)
10.5.3 消防站(Fire Station)
10.5.4 铁路(Railroads)
10.5.5 战争(War)
10.5.6 导游(Tourist Guide)
10.5.7 丰盛的晚餐(The Grand Dinner)
10.5.8 命题者的难题(The Problem With the Problem Setter)
10.6 提示
第11章 动态规划
11.1 慎用贪心法
11.2 编辑距离
11.3 重建路径
11.4 编辑距离的变种
11.5 程序设计举例:电梯优化
11.6 习题
11.6.1 越大越聪明?(Is Bigger Smarter?)
11.6.2 不同的子序列(Distinct Subsequences)
11.6.3 重量和力量(Weights and Measures)
11.6.4 单向TSP(Unidirectional TSP)
11.6.5 切割小木棍(Cutting Sticks)
11.6.6 渡船装载(Ferry Loading)
11.6.7 筷子(Chopsticks)
11.6.8 搬家大冒险:第四部(Adventures in Moving: Part Ⅳ)
11.7 提示
11.8 注解
第12章 网格
12.1 矩形网格
12.1.1 遍历
12.1.2 对偶图及其表示
12.2 三角形网格和六边形网格
12.2.1 三角形网格
12.2.2 六边形网格
12.3 程序设计举例:西餐碟的重量
12.4 给圆打包
12.5 经度和纬度
12.6 习题
12.6.1 棋盘上的蚂蚁(Ant on a Chessboard)
12.6.2 独轮车(The Monocycle)
12.6.3 六角星(Star)
12.6.4 蜜蜂Maja(Bee Maja)
12.6.5 抢劫案(Robbery)
12.6.6 (2/3/4)-维立方体?((2/3/4)-D Sqr/Rects/Cubes/Boxes?)
12.6.7 Dermuba三角(Dermuba Triangle)
12.6.8 航线(Airlines)
12.7 提示
第13章 几何
13.1 直线
13.2 三角形和三角学
13.2.1 直角三角形和勾股定理
13.2.2 三角函数
13.2.3 解三角形
13.3 圆
13.4 程序设计举例:超高速飞行
13.5 三角函数库
13.6 习题
13.6.1 狗拿地鼠(Dog and Gopher)
13.6.2 绳子王国的危机!(Rope Crisis in Ropeland!)
13.6.3 圆桌骑士(The Knights of the Round Table)
13.6.4 巧克力片饼干(Chocolate Chip Cookies)
13.6.5 生日蛋糕(Birthday Cake)
13.6.6 最大/最小的盒子(The Largest/Smallest Box…)
13.6.7 要算积分吗?(Is This Integration?)
13.6.8 它有多大?(How Big Is It?)
13.7 提示
第14章 计算几何
14.1 线段及其相交
14.2 多边形及旋转方向
14.3 凸包
14.4 三角剖分:算法与相关问题
14.4.1 Van Gogh算法
14.4.2 面积计算
14.4.3 点定位
14.5 网格上的算法
14.5.1 范围查询
14.5.2 网格多边形与Pick定理
14.6 几何函数库
14.7 习题
14.7.1 新生集会(Herding Frosh)
14.7.2 最近点对问题(The Closest Pair Problem)
14.7.3 电锯惊魂(Chainsaw Massacre)
14.7.4 冷热游戏(Hotter Colder)
14.7.5 没用的瓷砖打包公司(Useless Tile Packers)
14.7.6 雷达追踪(Radar Tracking)
14.7.7 岛上的树(Trees on My Island)
14.7.8 美味的牛奶(Nice Milk)
14.8 提示
附录A
A.1 ACM国际大学生程序设计竞赛
A.1.1 准备
A.1.2 战略战术
A.2 国际信息学奥林匹克
A.2.1 如何参加
A.2.2 比赛形式
A.2.3 准备
A.3 Topcoder.com
A.4 念研究生吧!
A.5 题目致谢
参考文献