信息学复赛备考总结.ppt

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,*,*,*,信息学复赛备考总结,,复赛本卷须知,,,1、认真审题，尤其要注意问题的规模〔数据范围〕，从某种意义上说，问题规模也暗示了你可能的算法数据小，也许是搜索派上用场的时候；数据大了，可能只能考虑动态规划，数学方法等高算法了2、正确的估计题目的难度和自己的水平拿到试题后先从总体上分析一下题目，做到心中有数！注意：题目的难易对所有人是公平的，只要最大限度地发挥自己的水平，不要有包袱，考出自己的最正确成绩3、正确地选择题目去做〔最擅长、最简单的先完成〕，合理地安排时间和解题顺序4、复赛中：一定提高正确率！！！解题速度是其次复赛考查的算法并不困难，建议大家：,,1〕 充分利用草稿纸，不要对自己的“心算能力〞太自信！编程熟练的同学喜欢“一气呵成〞，拿到题目就开始编码我认为这样不好，做信息学竞赛题的思维过程是丰富而曲折多变的，考虑问题必须全面，仅凭一时的“感觉〞来编程往往是漏洞百出比方初学者常常忘记做一些初始化工作〔远不止变量赋初值这种最简单的〕，即使有经验的同学也难免因一时疏忽写出几个错误的语句。

最要命的是“第一感觉〞的算法是错误的或者效率太低〔命题者的陷阱〕，而程序编了大半才发现，时间浪费了不说，还影响了信心和发挥2〕 做一些复杂的题目，编码采取自顶向下，逐步求精的方法，调试时采用输出中间结果的方法及时找出错误的地方可以这么说，思路越清晰，对自己程序的算法和编码越了解，调试也会越顺利〔一定不要无视这一点〕3〕 多测试：样例数据、极限〔小大〕数据、特殊数据，分析能否在规定的时空范围内出解，精度是否够，格式是否对，输入输出文件名、格式是否正确等4〕 不一定要拿总分值，有些题目如果你很拿手，也肯定能做对，那么一定要保证拿总分值；但有些题目，在有限的竞赛时间里，你很难拿总分值，或者自己觉得没有足够的时间和信心，没有好的方法，那么在很少的时间内用投机取巧的方法〔如贪心等〕能得到不错的分数，也是一种很大的成功题目 名称 算法 参考难度,,1997-c1 数矩形 数学〔乘法原理〕 *,,1997-c2 数字三角形 穷举 *,,1997-c3 数路径 递推〔迭代〕+加法原理+高精度 ***,,1997-g1 素数方阵 递归回溯+构造 **,,1997-g2 表达式判错 字符串+栈 **,,1997-g3 骑士游历 宽搜+递推 **,,1998-c1 1:2:3 穷举 *,,1998-c2 S! 高精度 *,,1998-c3 2的幂次方 递归+二进制 ***,,1998-g1 上下车问题 递推或者枚举 *,,1998-g2 连接多位数 贪心+字符串 **,,1998-g3 加法表 递归+直接判断 ***,,1999-c1 Cantor表 数学 *,,1999-c2/g2 回文数 字符串 **,,1999-c3/g3 旅行家的预算 贪心 ***,,1999-g1 导弹拦截 动态规划、贪心 **,,1999-g4 邮票面值设计 搜索+优化 ***,,2000-c1 计算器的改进 字符串 *,,2000-c2 税收与补贴问题 数学或穷举 **,,2000-c3/g2 乘积最大 动态规划+高精度 ***,,2000-c4/g3 单词接龙 回溯 **,,2000-g1 进制转换 类比+穷举 **,,2000-g4 方格取数 动态规划 ***,,2001-c1 数的计数 递归或递推或动态规划 *,,2001-c2 最大公约数与最小公倍数 穷举+优化+乘法原理 **,,2001-c3 二*树的先序序列 递归或穷举，构造 **,,2001-c4 装箱问题 宽搜+hash表，或动态规划 ***,,2001-g1 一元三次方程求解 穷举或随机化+迭代 **,,2001-g2 数的划分 递推或动态规划 **,,2001-g3 统计单词个数 贪心或随机化或动态规划 ***,,2001-g4 Car的旅行路线 图论〔Dijkstra算法〕 ***,,2002-c1 级数求和 高精度 *,,2002-c2 选数 搜索〔递归〕 ***,,2002-c3 产生数 乘法原理+图论 ***,,2002-c4 过河卒 递推+加法原理+高精度 **,,2002-g1 均分纸牌 数学 **,,2002-g2 字串变换 广搜〔双向〕+剪枝 ***,,2002-g3 自由落体 物理题 **,,2002-g4 矩形覆盖 搜索〔全国没有1人对〕 *****,,归纳：递推、动态规划、贪心、搜索、数学〔物理〕、图论、高精度、回溯、穷举、字符串,网上总结的一些心得,,二，编码采取自顶向下，逐步求精的方法，调试时采用输出中间结果的方法及时找出,,错误的地方。

可以这么说，思路越清晰，对自己程序的算法和编码越了解，调试也会,,越顺利〔一定不要无视〕三、最大限度的发挥自己的水平,,看上去是废话，但我必须说，当临近比赛的时候，这一点绝比照提高自己的编程能力,,重要和实际的多下面我谈谈从这几届分区联赛中得到的一些启示1.正确的估计题目的难度和自己的水平,,初学者常常“意气用事〔借用一下这个词吧〕〞，拿到一道看起来很“爽〞的题目就开始做,,了，其实这样不好记得NOI99第二试的时候许多项选择手一开始就做第三题 - 模拟题，,,看起来简单，其实要做好并不容易，所以 - 不少人用了4小时都没有做出来，只好...我,,虽然先做的第一题，但做完后也是去做第三题，做了3个小时却因为粗心...所以说，,,必须在平时训练一下对题目的规模，难点，编程调试复杂度等方面的估计，还要注意,,自己擅长哪方面，编程速度和准确度以及调试能力如何，结合自己对题目的估计，方,,能正确的选择题目和安排时间2.重视测试,,能够做的题目常常得不了总分值，这也属于发挥欠佳但其原因不是自我估计不准，,,而是考虑问题不全面一道自己有把握，有信心做好的题目一定要花大力气保证,,其正确性记得NOI99第一试，我第二题“几乎〞编正确了的，却因为初始化有误，,,我测试的数据可以通过，但评分时用的数据无一通过:( 。

这是因为我的测试数据,,太特殊，没有反映出程序的缺陷明白了吗？想想我的失败，大家一定要重视测,,试啊！,3.评分的唯一标准是测试数据,,我不是鼓励大家“投机取巧〞，我的意思是，一道困难,,的题目如果无法下手，在时间允许的情况下一定要写,,一个能解一些特殊情况的程序例如去年分区联赛?,,旅行家的预算?一题，无解的数据和没有加油站的数,,据各一个，难道对于这两个情况的程序你还不会编吗？,,得一些分算一些嘛还有“导弹追踪〞一题有一个数据,,是升序排列的，难道你不知道这种情况是一次只能打,,一个吗？很多最优化题目，不要一个字都不写，根据,,你的“直觉〞算法〔例如贪心〕，虽然得不了总分值，也,,能得一定的分数反正又不是写解题报告，得多少算,,多少4.不怕一万，就怕万一,,和编程序没有什么关系啦，我是提醒大家要多存盘什么的，,,最好保存一些不同版本〔例如算法不同〕的程序，便于选择,,修改不要不当回事，小心点总是好事我上次就因为...第,,二题编了两次〔好在只多花了10分钟〕,2.熟悉复赛的形式，内容和题目的特点,,复赛题目的特点是：,,第一题：算法比较明显的，或者和数学关系比较大的题目第二题：好上手，但程序量要大一点的题目，考虑全面也不容易。

第三题：一般是搜索，或者算法不明显的题目算法方面，可能考到的是：搜索(回溯就可以了),动态规划(几乎是必考),贪心,递推(小心真的考到哦),递归...数据结构反而考得不多熟悉字符串的操作和排序算法就差不多了3.选择自己最有潜力的方面专攻初学者是一般不可能做出所有的题目的，应该选一些自己平时最熟悉和有把握的题，一定要做对记住，信息学竞赛最容易出现“一失足成千古恨〞的情况自己熟悉的题目要加强编程熟练度，准确度，测试和调试能力，把自己有能力拿到的分拿稳假设我最近对回溯很有“感觉〞，我就应该多编一点回溯的程序。