信息学奥林匹克汇总课件

1、信息学奥林匹克（Olympiad in Informatics）简介成都七中 张君亮 About OIOI，即信息学奥林匹克(Olympiad in Informatics)OI的题目八皇后问题统计110000的数中末位为7的质数的个数And moreActivitiesOI的比赛、活动全国联赛(NOIP)省级选拔活动四川省冬令营(SCWC)四川省选拔赛(SCTSC)国家级竞赛活动全国竞赛(NOI)全国冬令营(WC)国家队选拔赛(CTSC)亚太地区竞赛(APIO)国际竞赛(IOI)DetailsNOIPSCWCSCTSCNOIWCAPIOCTSCIOINOIPNOIP，即全国青少年信息学奥林匹

2、克联赛(National Olympiad in Informatics in Provinces)NOIP每年由中国计算机学会统一组织，全国统一大纲、统一试卷，各省市、自治区都应参加联赛，参加联赛是参加NOI的必要条件。NOIP是普及性质的比赛，其成绩也会关系到其他一些比赛比赛分初赛和复赛初赛是笔试，主要考察基础知识复赛上机考试，内容为程序设计初赛于每年10月的最后一个星期六下午举行复赛于每年11月的最后一个星期六举行，提高上午、普及下午 NOIP分赛区评奖，设赛区一、二、三等奖联赛大纲NOIP大纲初赛复赛在初赛的内容上增加以下内容： 计算机的基本常识1计算机和信息社会（信息社会的主要特征、

3、计算机的主要特征、数字通信网络的主要特征、数字化）2信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）3信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构）4信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）5信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）6人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作）7信息技术的新发展、新特点、新应用等。计算机的基

4、本操作1. WINDOWS和LINUX的基本操作知识2. 互联网的基本使用常识 （网上浏览、搜索和查询等）3. 常用的工具软件使用（文字编辑、电子邮件收发等） 程序设计的基本知识数据结构1程序语言中基本数据类型(字符、整数、长整数、浮点)2. 浮点运算中的精度和数值比较3一维数组（串）与线性表4记录类型（PASCAL）/ 结构类型（C）程序设计1结构化程序设计的基本概念 2阅读理解程序的基本能力3具有将简单问题抽象成适合计算机解决的模型的基本能力4具有针对模型设计简单算法的基本能力5程序流程描述（自然语言/伪码/NS图/其他）6程序设计语言（PASCAL/C/C+）基本算法的处理1初等算法（计

5、数、统计、数学运算等）2排序算法（冒泡法、插入排序、合并排序、快速排序）3查找（顺序查找、二分法）4回溯算法数据结构1指针类型2多维数组3单链表及循环链表4二叉树5文件操作（从文本文件中读入数据，并输出到文本文件中） 程序设计1算法的实现能力2程序调试基本能力3设计测试数据的基本能力4程序的时间复杂度和空间复杂度的估计 算法处理1离散数学知识的应用（如排列组合、简单图论、数理逻辑）2分治思想3模拟法4贪心法5简单搜索算法（深度优先 广度优先）搜索中的剪枝6动态规划的思想及基本算法 SCWC SCTSCSCWC，即四川省冬令营(SiChuan Winter Camp)在每年寒假期间（2月）举行，

6、地点在成都或者绵阳内容主要为讲座和省集训队选拔省集训队选拔分两试，共选出12名省集训队选手（其中必须有2名女生）SCTSC，即四川省队选拔赛(SiChuans Team Selection Contest)省集训队选手参加每年6月初，成都共选出5男1女，作为四川省代表队参加NOI，同时选出2名夏令营选手NOINOI，即全国青少年信息学奥林匹克竞赛(National Olympiad in Informatics)时间一般为每年7月底至8月初，历时7天每一届都在全国不同城市举行NOI2008在浙江绍兴各省市自治区以及港澳地区都派出一个代表队参加主要活动有：参观、交流比赛团体对抗赛NOI比赛共有两

7、试，比赛评出一、二、三等奖（金银铜牌）以及优秀奖，前20名（即金牌的选手）进入国家集训队，有资格参加国家队选拔同期举行NOI夏令营和NOI网上同步赛Winter Camp 全国冬令营(Winter Camp)于每年寒假期间（1月）举行，举办地点为当年NOI承办地冬令营共8天，其中6天为培训和交流。参加冬令营的营员分：正式营员和非正式营员。获得NOI前20名的选手和指导教师为正式营员，非正式营员限量自愿报名参加（NOIP成绩相关）冬令营培训内容：包括授课、讲座、讨论、国家集训队论文答辩、测试论文答辩和测试的成绩关系到正式营员（国家集训队成员）参加国家队选拔的最后成绩APIO CTSCAPIO，即

8、亚太地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad)参加者为：国家集训队成员、NOIP成绩全国前50、各省的分配名额参赛者前6名作为中国队的正式选手，参加APIO评比，其余选手评中国赛区奖中国赛区的获奖比例同NOI，即金银铜牌比例分别为百分之十、二十和三十。 CTSC，即IOI中国队选拔赛(Chinas Team Selection Contest)，中国OI最高水平的竞赛5月中旬，北京CTSC分两试，第一试即为APIOIOI中国代表队（4人）的产生：论文、WC、作业、CTSC、面试IOIIOI，即国际信息学奥林匹克竞赛(International

9、Olympiad in Informatics)自1989年开始举办，每年8月举行，历时一星期每年由不同国家承办IOI2008在埃及各国派出代表队参加中国队的成绩辉煌算法知识分布 虽然2001年全国奥林匹克信息学竞赛中含许多可“一题多解” 的试题，但如果按照较优算法标准分类的话，大致可分为 算法分区联赛 全国赛 组队赛 物理题自由落体字符串处理字符近似查找 并查集与路径压缩银河英雄传说 模拟策略灭鼠行动回溯法选数、字串变换 购房计划 数学运算级数求和、 均分纸牌动态程序设计方法颁奖典礼贪吃的九头龙过河卒算法分区联赛 全国赛 组队赛 二分图的匹配玩具兵“构造法”解题调皮的小孩、新俄罗斯方块丹奇方

10、块 贪心法月亮森林数论（最大公约数）荒岛野人组合分析（欧拉函数）机器人M号几何计算（点和矩形的关系）矩形覆盖信息学奥林匹克竞赛特 点 1、凸现信息学知识和数学知识整合的趋势。 为了考核学生的数学能力，激发学生的创造力，2002年全国奥林匹克信息竞赛(NOI)、IOI组队赛和IOI，数论(荒岛野人)、组合分析(机器人M号)、图论类(玩具兵)的试题增加，并且首次出现了计算几何类的试题(矩形覆盖)。这说明信息学与数学的依赖关系日益凸现，数学素质好的人虽然不一定会编程，但希望学习编程的人愈来愈多；编程解题能力强的人势必有数学的潜质和爱好，他们中愈来愈多的人也希望深造数学。两门学科的交融和整合是奥林匹克

11、信息学活动发展的一个大趋势（有专家提议，数学教材讲算法，信息科技教材讲语言，上海的信息科技教材出现真值表（初中）和c语言（高中）。 “构造法”(调皮的小孩、新俄罗斯方块、丹奇方块 )或贪心策略类试题（月亮森林）的引入，使得算法知识的不确定性和不稳定性增加。这正体现了科学的本质知识是不断推陈出新的。2、算法知识的不确定性和不稳定性增加 试题的综合性增加，并不一定随知识的分类而发生变化，有时几乎找不到一个单一的经典算法(玩具兵通过最短路径构造二分图)，也找不到一个纯粹的数据结构问题（银河英雄传说 要求计算并查集中元素的相对位置），关键是你从哪个角度去分析，也就是说能不能综合所学的知识，应用自如地解

12、决问题。选手的综合素质愈高，得胜的机率愈大； 3、试题的综合性增加 经常面对着不知道算法的试题，面对着谁都不知如何处置的情境（经常出现许多选手在一题中得0分、优秀选手表现失常的情况），因此必须使学生正确地理解问题、深入问题的空间并形成解决问题的意识、习惯和能力。能不能创造性地应答没有遇到过的挑战，成为培训的基本要求和目标。4、创造性地应答没有遇到过的挑战信息学奥林匹克竞赛启 示 创造始于问题。“有了问题才会思考，有了思考才有解决问题的方法，才有找到独立思路的可能（陶行知）”。有问题虽然不一定有创造，但没有问题一定没有创造（想一想当前的解法有没有缺陷，有没有更好的算法，它与哪些问题有联系，与哪些

13、知识相关联，还可以拓延出哪些问题，要解决这些问题还需要哪些知识）；1、培养问题意识和问题能力。 如果恪守按部就班的培训程序，不谋求跳跃式学习，将离全国和国际奥林匹克信息学活动的前沿、离世界程序设计知识的前沿愈来愈远。因此在进行基础课程学习的同时，必须有追逐前沿的选择性学习。这里，有时候心理的障碍比科学上的障碍更难跨越，敢不敢的问题比能不能的问题更突出。其实在学习中或多或少地都有必要的跳跃，不少人还能够实现比较大的跳跃（ 2002年noi中的欧拉函数、冬令营营员讲的polya定理、博弈原理和遗传算法，爱笛生小学三年级退学、比尔.盖茨大学三年级退学）2、处理好前沿性与基础性、直线培训和散点培训、循

14、序渐进与跳跃式的矛盾。学生必须学会从浩如烟海的信息中选择最有价值的知识，构建个性化（符合自己能力结构和兴趣结构）和竞争需要的知识结构培训内容要有选择性，因为除了出题者，谁也说不清楚在未来竞赛中究竟什么知识是必要的（对基础的理解是主观的选择。例如中国、美国和俄罗斯的理科教材大不相同，有的同年级同学科的教材相差三分之二），因此不可能把所有重要的东西都选择好了给学生，而是应该将直线培训与散点培训相结合，选择部分重要的东西交给学生，让他们自己去探索若干知识点之间的联系，补充自己认为需要补充的知识。 3、参与活动的学生应由竞争关系和独立关系（你做你的，我干我的，程序和算法互相保密，彼此津津乐道于对方的失败和自己的成功）转向合作学习的关系（通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务）学生的心理调适：我掌握的知识仅不过是沧海一粟(进取心)；固守错误的概念比一无所知更可怕（明智）；三人之行必有我师（谦虚）；知识生产社会化条件下人的基本素质之一是合作精神（现在的重大科学发明需要成百上千科学家进行长期甚至跨国的合作，例如制作windows，人类基因工程）（现代意识）；前提条件：水平相当的同质成员或各有所长（包括数学知