信息学复赛备考总结课件

信息学复赛备考总结复赛注意事项1、认真审题，尤其要注意问题的规模（数据范围），从某种意义上说，问题规模也暗示了你可能的算法。数据小，也许是搜索派上用场的时候；数据大了，可能只能考虑动态规划，数学方法等高算法了。2、正确的估计题目的难度和自己的水平。拿到试题后先从总体上分析一下题目，做到心中有数！注意：题目的难易对所有人是公平的，只要最大限度地发挥自己的水平，不要有包袱，考出自己的最佳成绩。3、正确地选择题目去做（最擅长、最简单的先完成），合理地安排时间和解题顺序。4、复赛中：一定提高正确率！！！解题速度是其次。

复赛考查的算法并不困难，建议大家：1）充分利用草稿纸，不要对自己的“心算能力”太自信！编程熟练的同学喜欢“一气呵成”，拿到题目就开始编码。我认为这样不好，做信息学竞赛题的思维过程是丰富而曲折多变的，考虑问题必须全面，仅凭一时的“感觉”来编程往往是漏洞百出。比如初学者常常忘记做一些初始化工作（远不止变量赋初值这种最简单的），即使有经验的同学也难免因一时疏忽写出几个错误的语句。最要命的是“第一感觉”的算法是错误的或者效率太低（命题者的陷阱），而程序编了大半才发现，时间浪费了不说，还影响了信心和发挥。题目名称算法参考难度1997-c1数矩形数学（乘法原理）*1997-c2数字三角形穷举*1997-c3数路径递推（迭代）+加法原理+高精度***1997-g1素数方阵递归回溯+构造**1997-g2表达式判错字符串+栈**1997-g3骑士游历宽搜+递推**1998-c11:2:3穷举*1998-c2S!高精度*1998-c32的幂次方递归+二进制***1998-g1上下车问题递推或者枚举*1998-g2连接多位数贪心+字符串**1998-g3加法表递归+直接判断***1999-c1Cantor表数学*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-g4Car的旅行路线图论（Dijkstra算法）***2002-c1级数求和高精度*2002-c2选数搜索（递归）***2002-c3产生数乘法原理+图论***2002-c4过河卒递推+加法原理+高精度**2002-g1均分纸牌数学**2002-g2字串变换广搜（双向）+剪枝***2002-g3自由落体物理题**2002-g4矩形覆盖搜索（全国没有1人对）*****归纳：递推、动态规划、贪心、搜索、数学（物理）、图论、高精度、回溯、穷举、字符串网上总结的一些心得一、认真审题审题对于信息学竞赛来说尤其重要。同一个题目如果数据限制差异大的话，可能难度差异也很不同。例如：输入A,B,输出A+B的值。如果题目说0<=A,B<=10000,这道题目无疑是一道很简单的题目，但如果题目说0<=A,B<=10000000000000000000000000000000000000000000000显然就要用到高精度数的处理了。从某种意义上说，数据限制也暗示了你可能的算法。数据小，也许是搜索派上用场的时候，数据大了，可能只能考虑动态规划，数学方法等高效的算法了。

二、编码和调试的能力去年复赛的时候，我身边的那个选手，打键盘的声音特别大，引得我转过头去看他。这时，我正在写第一题，他已经写完开始调试了。我暗想，可能这是个极有竞争力的选手吧。当我完成第三题是不由自主的又去看他，竟发现他还在调试第一题。如此调试能力，试问如何能得高分？复赛考查的算法并不困难，选手在实现上的问题往往还要大一些。建议大家：一，充分利用草稿纸，不要对自己的“心算能力”太自信了。编程熟练的同学喜欢“一气呵成”，拿到题目就开始编码。我认为这样不好。做信息学竞赛竞赛题的思维过程是丰富而曲折多变的，考虑问题必须全面。仅凭一时的“感觉”来编程往往是漏洞百出。初学者常常忘记做一些初始化工作（远不止变量赋初值这种最简单的），即使有经验的同学也难免因一时疏忽写出几个错误的语句。最要命的是“第一感觉”的算法是错误的或者效率太低，而程序编了大半才发现...做一些复杂的题目（以前复赛的题目其实没有特别复杂的，但今后可说不准），大多数人多会在一分心的时候突然短了思路，不知道下一步该写什么了。3.评分的唯一标准是测试数据我不是鼓励大家“投机取巧”，我的意思是，一道困难的题目如果无法下手，在时间允许的情况下一定要写一个能解一些特殊情况的程序。例如去年分区联赛《旅行家的预算》一题，无解的数据和没有加油站的数据各一个，难道对于这两个情况的程序你还不会编吗？得一些分算一些嘛。还有“导弹追踪”一题有一个数据是升序排列的，难道你不知道这种情况是一次只能打一个吗？很多最优化题目，不要一个字都不写，根据你的“直觉”算法（例如贪心），虽然得不了满分，也能得