备战noip2006复赛（普及组）
一．联赛大纲
二．如何备战复赛
1. 做做以往历年的竞赛题和网上的模拟题，熟悉比赛的题型和要求，找出自己的不足，加强训练；
2. 增强自己编写代码和调试的熟练程度，提高做题的时间和节奏感；
3. 熟练掌握文件的输入/输出操作，新大纲中对复赛的要求；
4. 提高自己设计测试数据的能力；
5. 提高自己做题的正确率（分数/时间）；
6. 算法方面：递推、递归、动态规划、贪心、搜索（初中到回溯就差不多了）基本上是必考！！！对一些经典问题和算法，一定要熟练的不能再熟练；
7. 数据结构方面：字符串经常考，树（尤其二叉树）、图的基本算法（最短路径、最小生成树等）；
8. 如果有时间，可以全面复习（地毯式）
三．复赛注意事项
1.认真审题，尤其要注意问题的规模（数据范围），从某种意义上说，问题规模也暗示了你可能的算法。数据小（一般n<=25），也许是搜索派上用场的时候；数据大了，可能只能考虑动态规划，数学方法等高效算法了。
学会联想，一般求最值问题可以转化为斐波那契数列，栈可转化为组合数，杨晖三角形，卡特兰数。
2.正确的估计题目的难度和自己的水平。拿到试题后先从总体上分析一下题目，做到心中有数！
3.题目的难易对所有人是公平的，只要最大限度地发挥自己的水平，不要有包袱，考出自己的最佳成绩。考试时千万别去想名次，尤其别去想***大牛做得怎么样。要知道，只要你最大限度发挥自己水平，你的名次不会差的。
4.正确地选择题目去做（最擅长、最简单的先完成），合理地安排时间和解题顺序。
尤其别先做简单而又没把握的题，会耗时间，如果难题代码过长，可另当别论。
5.复赛中：一定提高正确率！！！解题速度是其次。做会做的题，就尽量保证能拿满分，不会做的题，可以用贪心，超时的搜索，尽量保证多拿分。
6.复赛考查的算法并不困难，选手在实现上的问题往往要多一些。
7.建议大家：
充分利用草稿纸，不要对自己的“心算能力”太自信！编程熟练的同学喜欢“一气呵成”，拿到题目就开始编码。我认为这样不好，做信息学竞赛题的思维过程是丰富而曲折多变的，考虑问题必须全面，仅凭一时的“感觉”来编程往往是漏洞百出。比如初学者常常忘记做一些初始化工作（远不止变量赋初值这种最简单的），即使有经验的同学也难免因一时疏忽写出几个错误的语句。最要命的是“第一感觉”的算法是错误的或者效率太低（命题者的陷阱），而程序编了大半才发现，时间浪费了不说，还影响了信心和发挥。
做一些复杂的题目，编码采取自顶向下，逐步求精的方法，调试时采用输出中间结果的办法及时找出错误的地方。可以这么说，思路越清晰，对自己程序的算法和编码越了解，调试也会越顺利（一定不要忽视这一点）。
多测试：样例数据、极限（小大）数据、特殊数据，分析能否在规定的时空范围内出解，精度是否够，格式是否对，输入输出文件名、格式是否正确等。
不一定要拿满分，有些题目如果你很拿手，也肯定能做对，那么一定要保证拿满分；但有些题目，在有限的竞赛时间里，你很难拿满分，或者自己觉得没有足够的时间和信心，没有好的方法，那么在很少的时间内用投机取巧的方法（如贪心等）能得到不错的分数，也是一种很大的成功。
8.第一题如果很难或很烦，可先放弃，这是一个很好的策略。要知道noip2006不仅考的是实力，是技术，还是心理，策略。
9.文件名切勿打错，认真检查。输出格式一定不能打错，仔细检查！！！
10.遇到error while linking错误信息，保存后重启计算机，再运行，若还出现，则先关掉fp,删除工作目录中的.bat和link，重启fp。若无效，就重启电脑，若还无效，立即向监考老师要求换机子。
遇到错误201,检查数组的范围是否太小了。
遇到错误106，检查读入格式是否出错。
若运行通过，算法正确，而没答案，则检查是否打了close语句
若程序中出现了halt语句，则之后一定要紧跟close语句，否则此程序不输出进文件。
尤其是递归程序结束前一定要打close！！！
11.做一段，保存一段。不要调试前还没保存。而且最好在另一个盘也保存一下。
12.提交文件只有.pas和.exe，注意：提交的件夹名字别打错，不要建子文件夹（否则没分）。
四．历年复赛题目总结
题目 名称 算法 参考难度
1997-c1 数矩形 数学（乘法原理） *
1997-c2 数字三角形 穷举 *
1997-c3 数路径 递推（迭代）+加法原理+高精度 ***
1998-c1 1:2:3 穷举 *
1998-c2 S! 高精度 *
1998-c3 2的幂次方 递归+二进制 ***
1999-c1 Cantor表 数学 *
1999-c2/g2 回文数 字符串 **
1999-c3/g3 旅行家的预算 贪心 ***
2000-c1 计算器的改良 字符串 *
2000-c2 税收与补贴问题 数学或穷举 **
2000-c3/g2 乘积最大 动态规划+高精度 ***
2000-c4/g3 单词接龙 回溯 **
2001-c1 数的计数 递归或递推或动态规划 *
2001-c2 最大公约数与最小公倍数 穷举+优化+乘法原理 **
2001-c3 二叉树的先序序列 递归或穷举，构造 **
2001-c4 装箱问题 宽搜+hash表，或动态规划 ***
2002-c1 级数求和 高精度 *
2002-c2 选数 搜索（递归） ***
2002-c3 产生数 乘法原理+图论 ***
2002-c4 过河卒 递推+加法原理+高精度 **
2003 乒乓球 模拟 *
2003 麦森数 高精度+数学知识 ***
2003 栈 数学公式/搜索（递归） **
2003 数字游戏 动态规划 ****
2004 不高兴的津津 统计 *
2004 花生采摘 排序 **
2004 火星人 排序（等进位） **
2004 FBI树 二叉树的性质+递推+递归 **
2005 陶陶摘苹果 统计 *
2005 校门外的树 离散数学+数组 *
2005 采药 动态规划/搜索+掐时 **
2005 循环 逐位逼近（ms很高深） *****
[p:1]
