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