信息学奥赛复赛备考策略.doc

信息学奥赛复赛备考策略信息学奥赛复赛备考策略复赛题目的特点是：第一题：算法比较明显的，或者和数学关系比较大的题目。第二题：好上手，但程序量要大一点的题目，考虑全面也不容易。第三和四题：一般是搜索，或者算法不明显的题目。 算法方面，可能考到的是：搜索(回溯就可以了)、动态规划(几乎是必考)、贪心、递推(小心真的考到)，递归，数据结构反而考得不多，熟悉字符串的操作和排序算法就差不多了。1、知识体系回顾，多做经典题目。在算法方面可能考到的是：搜索(回溯就可以了)、动态规划(几乎必考)、贪心、递推(小心真的考到)、递归、 简单的图论算法（dijkstra, MST, euler路等）、数据结构反而考得不多，熟悉字符串的操作和排序算法就差不多了。记住：信息学不是看会的，是练会的。一定要多看多想多练。2、养成编码和调试习惯。复赛考查的算法并不困难，选手在实现上的问题往往还要大一些。因此建议： 充分利用草稿纸，不要对自己的“心算能力”太自信了。编程熟练的同学喜欢“一气呵成”，拿到题目就开始编码，我认为这样不好。做信息学竞赛题的思维过程是丰富而曲折多变的，考虑问题必须全面。仅凭一时的“感觉”来编程往往是漏洞百出。初学者常常忘记做一些初始化工作（远不止变量赋初值这种最简单的），即使有经验的同学也难免因一时疏忽写出几个错误的语句。最要命的是“第一感觉”的算法是错误的或者效率太低，而程序编了大半才发现。做一些复杂的题目，大多数人多会在一分心的时候突然断了思路，不知道下一步该写什么了。 编码采取自顶向下，逐步求精的方法，调试时采用输出中间结果的办法及时找出错误的地方。可以这么说，思路越清晰，对自己程序的算法和编码越了解，调试也会越顺利（一定不要忽视）。多做套题，做单个题目和套题感觉并不一样。做套题要涉及到时间分配和做题顺序等，这些东西同样十分重要。3、最大限度发挥水平。 认真审题。审题对于信息学竞赛来说尤其重要。同一个题目如果数据限制差异大的话可能难度差异也很不同。例如：输入A、B，输出A+B的值。如果题目说0=A，B=10000，这道题目无疑是一道很简单的题目，但如果题目说0=A，B朴素搜索+(剪枝+备忘录+随机化) =贪心+(多种贪心方案找最优解)=不完全归纳求部分解+(非归纳部分CHEAT) =CHEAT+(RNDCHEAT)图:A最短路径 优先DIJSITRA,不会就FLOYD B最小生成树 PLIM KRUSKRAL 任意会一个就行,(NOIP的数据规模太让人变懒了) C其他的就具体问题具体分析了,(具体问题具体分析:高二政治考试活的灵魂)树:A遍历 .没什么可说的 其他的具体问题具体分析队列和栈:A排序 桶(适合数据范围在50000以内的)=快速(万能) =选择(两数据交换很费时的)=冒泡(省事的) B堆排序 单列出来就是因为它太适合需要N次排序但每次实质排序量很小的(合并果子) 其他的具体问题具体分析其他的具体问题具体分析4。写程序1.尽量1次写对，尤其避免诸如下述情况的错误：FOR I：=1 TO N DO READ（AN）；/你读N遍AN有意义吗。2.会的就别错在阴的测试数据上宁可评测的数据没这种情况,也不能你的程序不能处理评测的数据的特殊情况5。测试十分重要,避免100%会的问题漏特殊情况6。提示1.千万别装大牛,即使你是大牛 A.要随时保存,即使你能一次就AC B.就做会的部分,尝试新的优化方法