上海市控江中学王建德上海市控江中学王建德6、2002、2003年分区联赛复赛试题解析1、高精度运算2、图的运算3、搜索算法4、构造算法5、动态程序设计题型题目与课内知识相关自由落体、级数求和、乒乓球、麦森数字符串处理字符近似查找贪心法均分纸牌、传染病控制回溯法选数、字串变换、栈、神经网络、侦探推理动态程序设计方法过河卒、数字游戏、加分二叉树几何计算矩形覆盖虽然2002、2003年全国奥林匹克信息学复赛中含许多可“一题多解”的试题，但如果按照较优算法标准分类的话，大致可分为特点特点特点特点1、凸现信息学知识和学科知识整合的趋势。为了考核学生运用学科知识的能力，激发学生的创造力，2002、2003年全国奥林匹克信息联赛(NOIP)中学科类的试题增加，并且首次出现了计算几何类的试题((矩形覆盖矩形覆盖))。这说明信息学与学科的依赖关系日益凸现，学科基础好、尤其是数学素质好的人虽然不一定会编程，但希望学习编程的人愈来愈多；编程解题能力强的人势必有数学的潜质和爱好，他们中愈来愈多的人也希望深造数学。各门学科的交融和整合是奥林匹克信息学联赛活动发展的一个大趋势（按照2005年国家教改方案，数学教材增加算法内容，信息科技教材掺入语言知识）。2、“构造法”或贪心策略类试题的引入，使得算法知识的不确定性和不稳定性增加。这正体现了科学的本质—知识是不断推陈出新的。3、试题的综合性增加，并不一定随知识的分类而发生变化，有时几乎找不到一个单一的经典算法((字串变换字串变换————回溯法中有回溯法中有字符串处理字符串处理))，也找不到一个纯粹的数据结构问题（级数求和——需要为表达式的计算结果设计合适的（级数求和——需要为表达式的计算结果设计合适的数据类型）数据类型），关键是你从哪个角度去分析，也就是说能不能综合所学的知识，应用自如地解决问题。选手的综合素质愈高，得胜的机率愈大；4、经常面对着不知道算法的试题，面对着谁都不知如何处置的情境（经（经常出现许多选手在一题中得常出现许多选手在一题中得00分、优秀选手表现失常的情分、优秀选手表现失常的情况况）），因此必须使学生正确地理解问题、深入问题的空间并形成解决问题的意识、习惯和能力。能不能创造性地应答没有遇到过的挑战，成为培训的基本要求和目标。1、培养问题意识和问题能力。创造始于问题。“有了问题才会思考，有了思考才有解决问题的方法，才有找到独立思路的可能（陶行知）”。有问题虽然不一定有创造，但没有问题一定没有创造（想一想当前的解法有没有缺陷，有没有更好的算法，它（想一想当前的解法有没有缺陷，有没有更好的算法，它与哪些问题有联系，与哪些知识相关联，还可以拓延出哪些与哪些问题有联系，与哪些知识相关联，还可以拓延出哪些问题，要解决这些问题还需要哪些知识）问题，要解决这些问题还需要哪些知识）；启示启示启示启示2、处理好前沿性与基础性、直线培训和散点培训、循序渐进与跳跃式的矛盾。如果恪守按部就班的培训程序，不谋求跳跃式学习，将离全国和国际奥林匹克信息学活动的前沿、离世界程序设计知识的前沿愈来愈远。因此在进行基础课程学习的同时，必须有追逐前沿的选择性学习。这里，有时候心理的障碍比科学上的障碍更难跨越，敢不敢的问题比能不能的问题更突出。其实在学习中或多或少地都有必要的跳跃，不少人还能够实现比较大的跳跃（（爱笛生小学三年级退学、比尔爱笛生小学三年级退学、比尔..盖茨大学三年级退学）盖茨大学三年级退学）学生必须学会从浩如烟海的信息中选择最有价值的知识，构建个性化（符合自己能力结构和兴趣结构）和竞争需要的知识结构培训内容要有选择性，因为除了出题者，谁也说不清楚在未来竞赛中究竟什么知识是必要的（对基础的理解是主观的选择。例如中国、美国和俄罗斯的理科教材（对基础的理解是主观的选择。例如中国、美国和俄罗斯的理科教材大不相同，有的同年级同学科的教材相差三分之二）大不相同，有的同年级同学科的教材相差三分之二），因此不可能把所有重要的东西都选择好了给学生，而是应该将直线培训与散点培训相结合，选择部分重要的东西交给学生，让他们自己去探索...
