信息学奥赛复赛备考策略
信息学奥赛复赛备考策略
复赛题目的特点是：
第一题：算法比较明显的，或者和数学关系比较大的题目。
第二题：好上手，但程序量要大一点的题目，考虑全面也不容易。
第三和四题：一般是搜索，或者算法不明显的题目。算法方面，可能考到的是：搜索(回溯就可以了)、动态规划(几乎是必考)、贪心、递推(小心真的考到)，递归……，数据结构反而考得不多，熟悉字符串的操作和排序算法就差不多了。
1、知识体系回顾，多做经典题目。在算法方面可能考到的是：搜索(回溯就可以了)、动态规划(几乎必考)、贪心、递推(小心真的考到)、递归、简单的图论算法（dijkstra, MST, euler路等）、数据结构反而考得不多，熟悉字符串的操作和排序算法就差不多了。记住：信息学不是看会的，是练会的。一定要多看多想多练。
2、养成编码和调试习惯。复赛考查的算法并不困难，选手在实现上的问题往往还要大一些。因此建议：
①充分利用草稿纸，不要对自己的“心算能力”太自信了。编程熟练的同学喜欢“一气呵成”，拿到题目就开始编码，我认为这样不好。做信息学竞赛题的思维过程是丰富而曲折多变的，考虑问题必须全面。仅凭一时的“感觉”来编程往往是漏洞百出。初学者常常忘记做一些初始化工作（远不止变量赋初值这种最简单的），即使有经验的同学也难免因一时疏忽写出几个错误的语句。最要命的是“第一感觉”的算法是错误的或者效率太低，而程序编了大半才发现……。做一些复杂的题目，大多数人多会在一分心的时候突然断了思路，不知道下一步该写什么了。
②编码采取自顶向下，逐步求精的方法，调试时采用输出中间结果的办法及时找出错误的地方。可以这么说，思路越清晰，对自己程序的算法和编码越了解，调试也会越顺利（一定不要忽视）。
③多做套题，做单个题目和套题感觉并不一样。做套题要涉及到时间分配和做题顺序等，这些东西同样十分重要。
3、最大限度发挥水平。
①认真审题。审题对于信息学竞赛来说尤其重要。同一个题目如果数据限制差异大的话可能难度差异也很不同。例如：输入A、B，输出A+B的值。如果题目说0<=A，B<=10000，这道题目无疑是一道很简单的题目，但如果题目说0<=A，B<=10^100则显然就要用到高精度数的处理了。从某种意义上说，数据限制也暗示了可能的算法，数据小，也许是搜索派上用场的时候，数据大了，可能只能考虑动态规划、数学方法等高效的算法了。
②正确估计题目的难度和自己的水平。初学者是一般不可能做出所有题目的，应该选一些平时最熟悉和有把握的题，一定要做对。熟悉的题目要加强编程熟练度、准确度、测试和调试能力，把自己有能力拿到的分拿稳。初学者常常“意气用事”，拿到一道看起来很“爽”的题目就开始做了，其实这样不好。平时必须训练一下对题目的规模、难点、编程调试复杂度等方面的估计，还要注意自己擅长哪方面，编程速度和准确度以及调试能力如何，结合自己对题目的估计，方能正确的选择题目和安排时间。
③重视测试。能够做的题目常常得不了满分，这也属于发挥欠佳。究其原因不是自我估计不准，而是考虑问题不全面，一道自己有把握，有信心做好的题目一定要花大力气保证其正确性。测试的数据既要考虑一般，也要考虑特殊情况，评分的唯一标准是测试数据。一道困难的题目如果无法下手，在时间允许的情况下一定要写一个能解一些特殊情况的程序。很多最优化题目，不要一个字都不写，根据“直觉”算法（如贪心），虽然得不了满分，也能得一定的分数。反正又不是写解题报告，得多少算多少。
④编程过程中注意随时存盘。最好保留一些不同版本（如算法不同）的程序，便于选择修改。
做复赛题的步骤(个人的经验)
1。看题（非水，很重要）
至少要看3遍
第1遍把文件名和输入输出打对了，
并且要看清楚输入输出的规模，数据类型（直接关系你能得多少分的细节）
第2遍确定自己会不会做，判断在不cheat的情况下能出多少分
第3遍为分析做准备
100%会的就不废话了
50%会（算法会，但不可能过大数据点）就先把30%的数据ac了
20%会（算法只会一些特殊情况的）就先ac这些
0%会（。。。。。。偶看不懂啊。。）就cheat+rnd把。。。。
2。分析
1;找关键字
比如"最短" 还有那些公式比如神经网络的那个求和
2;根据关键字判断抽象数据结构
图,2X树,队列和环,ETC.
3;根据抽象数据结构判断算法和具体数据模型
想不出抽象数据结构的题基本考试算法思考顺序:
数学方法(包括动态规划)=>朴素搜索+(剪枝+备忘录+随机化)
=>贪心+(多种贪心方案找最优解)=>不完全归纳求部分解+(非归纳部分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（A[N]）；的就别错在阴的测试数据上
宁可评测的数据没这种情况,也不能你的程序不能处理评测的数据的特殊情况
5。测试
十分重要,避免100%会的问题漏特殊情况
6。提示
1.千万别装大牛,即使你是大牛
A.要随时保存,即使你能一次就AC
B.就做会的部分,尝试新的优化方法那是赛后的事情
C.不要认为任1道题你做过,即使你真的做过,把每道题
2.不要在考试的时候想别的事情,考场就是战场,秒的错过就是你1生的追悔莫及