信息学竞赛中如何提高审题能力
合肥奥数网整理
2011-09-30 16:35:20
信息学竞赛是对每一位学生综合能力的检测，包括分析问题、发现规律、确定算法、编写程序、测试完善等各方面，在比赛中需格外小心，特别是审题需仔细分析确定算法。指导学生在审题环节应注意以下问题：
1.根据题目考虑时间复杂度、空间复杂度及范围。尤其要注意问题的规模（数据范围）。从某种意义上说，问题规模也暗示了你可能的算法。数据小（一般n≤25），也许是搜索派上用场的时候；数据大，只能考虑动态规划、数学方法等高效算法。有些根据数据规模可能要用上高精度。如最短路径(城市交通)有N个城市，编号1-n，有些城市之间有路相连，有些则无，有路则当然有一个距离。下图为一个含有11个城市的图，连线上的数(权)表示距离。现在规定只能从编号小的城市到编号大的城市，问你从编号为1的城市到编号为n的城市之间的最短距离是多少？ 键盘输入第一行为n,表示城市数，n≤200,下面的N行是一个n*n 的邻接矩阵map[I,j],其中map[I,j]=0表示城市I和城市J之间没有相连，否则为两者之间的距离。这个题目用深搜可以过部分点，但要想全部点都过，只能用动态规划。
2.考虑问题是否有隐含条件并进行优化。问题描述是题目的关键，含有解决问题的条件。解题关键是将条件认真分析、加以整理，发现隐藏在其中的规律。先将可能出现的各种情况一一列举，再构思解答问题所必需的模型。这是解题的基础，也是解题的核心。学生必须在这个环节上花大量时间，形成自己的思路后才去做题，切忌边编程边思考。
3.根据自身水平，能过多少点就过多少点，选择适合自己的算法，比赛切忌强求。要求学生在比赛中根据自己的实力，如上例中，假如你不会用动态规划的状态转移方程，那么就直接用深搜吧，至少可以过一部分的点。
推荐阅读：
