信息学奥赛复赛备考策略

《信息学奥赛复赛备考策略》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、信息学奥赛复赛备考策略信息学奥赛复赛备考策略复赛题目的特点是：第一题：算法比较明显的，或者和数学关系比较大的题目。第二题：好上手，但程序量要大一点的题目，考虑全面也不容易。第三和四题：一般是搜索，或者算法不明显的题目。算法方面，可能考到的是：搜索(回溯就可以了)、动态规划(几乎是必考)、贪心、递推(小心真的考到)，递归……，数据结构反而考得不多，熟悉字符串的操作和排序算法就差不多了。1、知识体系回顾，多做经典题目。在算法方面可能考到的是：搜索(回溯就可以了)、动态规划(几乎必考)、贪心、递推(小心真的考到)、递

2、归、简单的图论算法（dijkstra,MST,euler路等）、数据结构反而考得不多，熟悉字符串的操作和排序算法就差不多了。记住：信息学不是看会的，是练会的。一定要多看多想多练。2、养成编码和调试习惯。复赛考查的算法并不困难，选手在实现上的问题往往还要大一些。因此建议：①充分利用草稿纸，不要对自己的“心算能力”太自信了。编程熟练的同学喜欢“一气呵成”，拿到题目就开始编码，我认为这样不好。做信息学竞赛题的思维过程是丰富而曲折多变的，考虑问题必须全面。仅凭一时的“感觉”来编程往往是漏洞百出。初学者常常忘记做一些初始

3、化工作（远不止变量赋初值这种最简单的），即使有经验的同学也难免因一时疏忽写出几个错误的语句。最要命的是“第一感觉”的算法是错误的或者效率太低，而程序编了大半才发现……。做一些复杂的题目，大多数人多会在一分心的时候突然断了思路，不知道下一步该写什么了。②编码采取自顶向下，逐步求精的方法，调试时采用输出中间结果的办法及时找出错误的地方。可以这么说，思路越清晰，对自己程序的算法和编码越了解，调试也会越顺利（一定不要忽视）。③多做套题，做单个题目和套题感觉并不一样。做套题要涉及到时间分配和做题顺序等，这些东西同样十分重

4、要。 3、最大限度发挥水平。①认真审题。审题对于信息学竞赛来说尤其重要。同一个题目如果数据限制差异大的话可能难度差异也很不同。例如：输入A、B，输出A+B的值。如果题目说0<=A，B<=10000，这道题目无疑是一道很简单的题目，但如果题目说0<=A，B<=10^100则显然就要用到高精度数的处理了。从某种意义上说，数据限制也暗示了可能的算法，数据小，也许是搜索派上用场的时候，数据大了，可能只能考虑动态规划、数学方法等高效的算法了。②正确估计题目的难度和自己的水平。初学者是一般不可能做出所有题目的，应该选一些平

5、时最熟悉和有把握的题，一定要做对。熟悉的题目要加强编程熟练度、准确度、测试和调试能力，把自己有能力拿到的分拿稳。初学者常常“意气用事”，拿到一道看起来很“爽”的题目就开始做了，其实这样不好。平时必须训练一下对题目的规模、难点、编程调试复杂度等方面的估计，还要注意自己擅长哪方面，编程速度和准确度以及调试能力如何，结合自己对题目的估计，方能正确的选择题目和安排时间。③重视测试。能够做的题目常常得不了满分，这也属于发挥欠佳。究其原因不是自我估计不准，而是考虑问题不全面，一道自己有把握，有信心做好的题目一定要花大力气保

6、证其正确性。测试的数据既要考虑一般，也要考虑特殊情况，评分的唯一标准是测试数据。一道困难的题目如果无法下手，在时间允许的情况下一定要写一个能解一些特殊情况的程序。很多最优化题目，不要一个字都不写，根据“直觉”算法（如贪心），虽然得不了满分，也能得一定的分数。反正又不是写解题报告，得多少算多少。④编程过程中注意随时存盘。最好保留一些不同版本（如算法不同）的程序，便于选择修改。做复赛题的步骤(个人的经验)1。看题（非水，很重要）至少要看3遍第1遍把文件名和输入输出打对了，并且要看清楚输入输出的规模，数据类型（直接关

7、系你能得多少分的细节）第2遍确定自己会不会做，判断在不cheat的情况下能出多少分第3遍为分析做准备　100%会的就不废话了　50%会（算法会，但不可能过大数据点）就先把30%的数据ac了　20%会（算法只会一些特殊情况的）就先ac这些　0%会（。。。。。。偶看不懂啊。。）就cheat+rnd把。。。。2。分析1;找关键字　比如"最短"还有那些公式比如神经网络的那个求和2;根据关键字判断抽象数据结构　图,2X树,队列和环,ETC.3;根据抽象数据结构判断算法和具体数据模型　想不出抽象数据结构的题基本考试算法思考

8、顺序:　数学方法(包括动态规划)=>朴素搜索+(剪枝+备忘录+随机化)　=>贪心+(多种贪心方案找最优解)=>不完全归纳求部分解+(非归纳部分CHEAT)　=>CHEAT+(RNDCHEAT)　图:A最短路径优先DIJSITRA,不会就FLOYD　　B最小生成树PLIMKRUSKRAL任意会一个就行,(NOIP的数据规模太让人变懒了)　　C其他的就具体问题具体分析了,(具体问题具体分析