本书是为广大参加信息学奥林匹克联赛的学生和指导老师精心准备的一本书。本书内容全面，基本涵盖了复赛涉及的所有知识点，着重于实用与实战，在算法分析和应用上，简明扼要，细致清晰，便于学生自学和教师上课；在习题指导上，提供详细的解题步骤、标程及测试数据，便于学生上机练习。全书共分为三个模块，分别为经典问题与算法设计、模拟训练题和模拟训练题分析及参考程序。

第1讲 时空分析
信息学竞赛有个特色，它的题目原型与计算机无关，而是与学习、生活息息相关。拿到题目后，需要把题目的模型转换成能用程序语言描述的算法或数据结构。在设计解决问题的方法时，可以采用不同的算法，例如*小生成树有Prim、Kruskal算法，排序有快排、桶排、插入排序等算法。方法不一样，程序计算的工作量就不一样。采用什么样的方法，才是有效的?评价一个方法的好坏，可以从时间复杂度和空间复杂度来判别。有的方法只需耗时l秒钟，有的方法却需耗时10秒钟；有的方法只需耗费10MB的空间，有的方法却需耗费1GB的空间。我们认为耗费时间、空问越小，算法越优。
一、时间复杂度
时间复杂度又称计算复杂度，是指执行程序的计算工作量。同一问题，采用不同的算法，程序的计算工作量是不一样的。衡量一个算法的时间复杂度，可以采用两种方法：执行时间和执行运算次数。执行时间，指在计算机上运行程序从开始到结束所花费的时间。执行时间与��算机配置有关，配置越高的机器，运算速度越快，执行时间就越少，反之越多。因计算机配置差异太大，这种方法可取性不高。执行运算次数是根据程序中执行指令条数和语句条数来度量的，它大致等于计算机执行一种简单操作所需时间与算法中简单操作次数的乘积。这种方法不以计算机的配置为依据，而以算法中的操作次数总耗时为依据，耗时越少，执行时间越快；耗时越多，执行时间越慢。这种方法已经被作为衡量时间复杂度的*有效方法。每年NOl的所有比赛，中国计算机学会(CCF)都会把评测机的详细配置放在NOl官网上，供选手们根据算法来预测程序的执行时间。
……

经典问题与算法设计
第1讲 时空分析
第2讲 排序算法
第3讲 线性数据结构
第4讲 树型结构的应用
第5讲 并查集
第6讲 区间问题
第7讲 *小生成树问题
第8讲 *短路径问题
第9讲 分治法
第10讲 搜索法
第11讲 贪心法
第12讲 离散优化
第13讲 Hash优化
第14讲 线性动态规划
第15讲 区间型动态规划
第16讲 坐标型动态规划
第17讲 背包型动态规划
第18讲 树型动态规划
模拟训练题
全国信息学分区联赛模拟试题(一)
全国信息学分区联赛模拟试题(二)
全国信息学分区联赛模拟试题(三)
全国信息学分区联赛模拟试题(四)
全国信息学分区联赛模拟试题(五)
全国信息学分区联赛模拟试题(六)
全国信息学分区联赛模拟试题(七)
全国信息学分区联赛模拟试题(八)
全国信息学分区联赛模拟试题(九)
全国信息学分区联赛模拟试题(十)
模拟训练题分析及参考程序
全国信息学分区联赛模拟试题(一)
全国信息学分区联赛模拟试题(二)
全国信息学分区联赛模拟试题(三)
全国信息学分区联赛模拟试题(四)
全国信息学分区联赛模拟试题(五)
全国信息学分区联赛模拟试题(六)
全国信息学分区联赛模拟试题(七)
全国信息学分区联赛模拟试题(八)
全国信息学分区联赛模拟试题(九)
全国信息学分区联赛模拟试题(十)