文档介绍：2003年信息学竞赛回眸
上海市控江中学王建德
2004年国际奥林匹克信息学竞赛中国集训队冬令营
目录
2003年竞赛试题的概况
2003NOIP提高组的试题解析
2003IOI的试题解析
2003年竞赛的知识结构分布
竞赛
试题
算法
NOIP
乒乓球
数据统计
NOIP
数字游戏
动态程序设计
NOIP
栈
回溯法或组合数学的Catalan数
NOIP
麦森数
高精度运算
NOIP
神经网络
图的递归运算
NOIP
侦探推理
回溯法
NOIP
加分二叉树
递归的动态程序设计
NOIP
传染病扩展
回溯法
竞赛
试题
算法
IOI
可视边界
线段树
IOI
代码转换
程序语句在满足加法交换率和变量名改换情况下的匹配
IOI
猜牛游戏
贪心或类博弈树算法
IOI
路径维护
在无向图的生成过程过程中计算最小生成树
IOI
逆向输出
开放性试题
IOI
机器人
宽度优先搜索
2003年竞赛的知识结构分布
竞赛
试题
算法
NOI
木棒游戏
枚举搜索
NOI
文本编辑器
数据结构
NOI
卫星探测
图形几何与二分查找
NOI
草莓
动态程序设计(链)、贪心、二分法(树)和背包(完全图)
NOI
数据生成器
前序遍历和后序遍历
NOI
智破连环阵
回溯法
2003年竞赛的知识结构分布
试题特点
1、  强调基础知识的灵活应用。每一轮竞赛都有基础知识题,但对灵活应用基础知识的要求愈来愈高。例如IOI的《路径维护》在逐边添入无向图的过程中计算最小生成树;《文本编辑器》要求设计多样的数据结构。例如线性表、非线性的树和图;NOIP的《加分二叉树》采用的动态程序设计是递归形式的;NOI的《数据生成器》必须综合使用前序遍历和后序遍历
2、  首次出现了线段树和可以选择类博弈树算法的试题
3、  近似算法类的试题增加。例如IOI的《猜牛游戏》、《逆向输出》、《机器人》、NOI的《卫星探测》、《草莓》、《智破连环阵》等。由于这些例题视程序逼近最优解和最优效率的程度给分,因此拓展了选手思维的空间,易启发选手的创造性。但反过来说,由于近似算法类的选题空间比较大,因此有可能使得题目的难度加大。
试题特点
4、树形结构类的问题增多。例如NOI的《卫星探测》通过二分查找构造一棵隐形的二叉树;《草莓》和《数据生成器》使用了人们容易被忽视的后序遍历;IOI的《路径维护》要求计算最小生成树;
5、可“一题多解”和开放性的试题增多。例如,IOI的《逆向输出》就是一道没有固定模式和经典算法可套用、需要量身定制合适算法的试题;《猜牛游戏》既可以采用贪心法,亦可以采用类博弈树的算法;NOIP的《栈》既可以通过回溯法计算,亦可以通过组合数学的Catalan数计算;
6、出现一些“陷阱题”。例如NOIP的《传染病扩展》极易诱导选手错误地使用贪心法或动态程序设计,实际上该问题不具备最优子结构的特征,正确的算法是回溯搜索。
启示
培养内省智力
充分利用网络资源
以问题为出发点、以自主探究为途径、以构造网络式思维模式为基础、以创新为目的组织集训
培养内省智力
入门自信心
提高自省力
自信心和自知之明是对立的统一。自信心倘若不是建立在自知之明的基础上,则会变成一种无知的自负,不可能取得持续的成功。
科学精神的核心是怀疑和批评。这种态度既对他人又对自己,“知人者智,自知者明”,“知常曰明”
不能用“看书”取代“上机实践”,不能用“读懂”等同“会做”。经常要想:自己怎样面对这个问题的挑战;如果由自己当场独立解题的话,会得到怎样的结果。纸上得来终觉浅,绝知此事要躬行。看懂了不稀奇,会做有灵气,能讲清原理、提出质疑、拓延思路、探索新知才算了不起
在挑选练****题时,既不要因为轻视而放弃基础题;也不要因为畏难而放弃大题难题。
充分利用网络上与信息学活动相关的信息资源
1、由于网络上大量的算法知识和试题的出现,使得学生学****的大部分时间和空间由课堂转移到网上学****自主性显著提高,学****方式发生了根本性的变化
2、学****的效率取决于如何在浩如烟海的网上信息选择适应于竞赛需要和个性发展的东西
3、千万不要有“太易了不屑做、太难了不愿做”的主观随意性