首页 > 图书中心 > 挑战编程:程序设计竞赛训练手册

目录

第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}

版权所有(C)2019 清华大学出版社有限公司 京ICP备10035462号 京公网安备11010802013248号

联系我们 | 网站地图 | 法律声明 | 友情链接 | 盗版举报 | 人才招聘