信息学奥林匹克竞赛指导 2001竞赛试题解析PDF电子书下载

第1章 数学分析 1

1.1解方程 1

例题1反正切函数的应用（全国赛） 1

例题2一元三次方程求解（分区联赛） 3

1.2逻辑推理 5

例题3聪明的学生（组队赛） 5

1.3初等数论 9

例题4最大公约数与最小公倍数问题（分区联赛） 9

1.4组合分析 11

例题5数的计数（分区联赛） 11

例题6 Twofive（国际赛） 12

1.5线性代数 19

例题7 GPA排名系统（组队赛） 19

例题8求前序排列（分区联赛） 29

2.1二叉树的遍历 29

第2章 数据结构 29

2.2并查集与路径压缩 31

例题9食物链（全国赛） 31

2.3树状数组 35

例题10移动电话（国际赛） 35

2.4最短路径问题 43

例题11 Car的旅行路线（分区联赛） 44

2.5哈希表 49

例题12方程的解数（全国赛） 50

例题13双重加密（国际赛） 54

例题14查找后继词（组队赛） 62

2.6博弈树 68

例题15 Ioiwari游戏（国际赛） 69

第3章 动态程序设计方法 78

例题16统计单词个数（分区联赛） 79

3.1按自下而上方式求最优解 79

例题17装箱问题（分区联赛） 82

3.2通过动态程序设计方法枚举所有方案 85

例题18数的划分（分区联赛） 85

例题19陨石的秘密（全国赛） 89

3.3状态的选定 93

例题20炮兵阵地（全国赛） 93

3.4状态的存储 99

例题21排序二叉树（组队赛） 99

3.5动态程序设计与博弈树 105

例题22取分（国际赛） 105

第4章 搜索 112

4.1宽度优先搜索 112

例题23聪明的打字员（全国赛） 112

4.2回溯法 116

例题24 Depot（国际赛） 117

例题25 逻辑电路最优设计（组队赛） 123

第5章 网络流 134

例题26终极情报网（组队赛） 134

第6章 2001年国际奥林匹克信息学竞赛中国集训队辅导讲义 143

6.1图论 143

6.1.1构造模型 143

6.1.2模型转化 156

6.1.3小结 164

6.2动态规划 164

6.2.1理论基础 165

6.2.2适用动态规划解题的问题性质 165

6.2.3阶段的划分 168

6.2.4状态的选取 172

6.2.5状态的存储 176

6.2.6状态转移方程的优化 184

6.2.7多进程的最优化决策问题 186