信息学奥林匹克竞赛

1、信息学 奥林匹克竞赛2014.03.16u交流内容：一一. . 信息学奥林匹克竞赛赛事介绍信息学奥林匹克竞赛赛事介绍二二. . 目前我省信息学奥赛开展情况目前我省信息学奥赛开展情况三三. . 考试内容考试内容四四. . 学生的选拔与组织学生的选拔与组织五五. . 辅导进度与时间安排辅导进度与时间安排六六. . 对辅导老师的一点建议对辅导老师的一点建议七七. . 问题解答问题解答 高中阶段五科奥林匹克竞赛：高中阶段五科奥林匹克竞赛： 数学、物理、化学、生物、数学、物理、化学、生物、信息学信息学全国联赛（省赛区）全国联赛（省赛区）全国竞赛全国竞赛一 .信息学奥林匹克竞赛赛事介绍u1、省赛区的竞赛名

2、称 全国高中数学联赛；全国高中数学联赛； 全国中学生物理竞赛全国中学生物理竞赛(省级赛区省级赛区)； 全国高中学生化学竞赛全国高中学生化学竞赛(省级赛区省级赛区)； 全国青少年信息学奥林匹克联赛全国青少年信息学奥林匹克联赛； 全国中学生生物学联赛。全国中学生生物学联赛。 u2. 全国决赛的名称 中国数学奥林匹克；中国数学奥林匹克； 全国中学生物理竞赛决赛；全国中学生物理竞赛决赛； 全国高中学生化学竞赛；全国高中学生化学竞赛； 全国青少年信息学奥林匹克竞赛；全国青少年信息学奥林匹克竞赛； 全国中学生生物学竞赛。全国中学生生物学竞赛。 国家对获奖学生的政策：u高中2013届（2010级）前： 高中

3、阶段：高中阶段：学科奥林匹克竞赛：学科奥林匹克竞赛： 下列两个之一就具备保送资格：下列两个之一就具备保送资格： 省赛区中获得一等奖省赛区中获得一等奖 全国决赛一、二、三等奖全国决赛一、二、三等奖的应届高中毕业生的应届高中毕业生u2011级开始： 参加全国决赛进入国家集训队保送（全国前参加全国决赛进入国家集训队保送（全国前50，金牌），金牌） 金银铜高考加金银铜高考加20分分 省赛区联赛一等奖不再具有保送资格省赛区联赛一等奖不再具有保送资格 大学有自己的自主招生政策（单独）大学有自己的自主招生政策（单独）信息学奥林匹克竞赛信息学奥林匹克竞赛 面向全国中学生的一种竞赛活动，旨在激发中学生在计算机科

4、学方面的兴趣，培养他们逻辑思维的能力，给那些有才华的学生提供相互交流和学习的机会，通过竞赛和相关的活动培养和选拔优秀的计算机后备人才。信息学奥林匹克竞赛赛事：信息学奥林匹克竞赛赛事：1.NOIP1.NOIP（全国信息学奥林匹克联赛）（全国信息学奥林匹克联赛） National Olympiad in Informatics in Provinces 2.NOI 2.NOI （全国信息学奥林匹克竞赛）（全国信息学奥林匹克竞赛） National Olympiad in Informatics3.IOI 3.IOI （国际信息学奥林匹克竞赛）（国际信息学奥林匹克竞赛） International

5、Olympiad in Informatics NOIP分区联赛 初赛：初赛： 10月中旬（周六下午月中旬（周六下午2:30-4:30） 笔试（笔试（100分）分） 资格赛，地市独立组织（全国统一命题，统一时间）资格赛，地市独立组织（全国统一命题，统一时间） 复赛：复赛： 11月份中旬（第二周月份中旬（第二周,周六、周日上午周六、周日上午8:30-12:00） 两试（上机）两试（上机） 每试每试3个题目，每题个题目，每题100分，共分，共600分分 提交源程序，黑盒子测试法提交源程序，黑盒子测试法 各省统一组织考试各省统一组织考试 全国统一评测全国统一评测uNOI全国赛： 7月底举行（两试月底

6、举行（两试,每试每试3个题目，每试个题目，每试5小时）小时） 每个省选拔队员参加每个省选拔队员参加10-15名名 我省从上一年参加我省从上一年参加NOIP的获得一等奖的选手中经过两次的获得一等奖的选手中经过两次选拔赛选拔当年参加选拔赛选拔当年参加NOI的队员的队员 4月份，月份，5月份两次选拔赛月份两次选拔赛二. 目前我省信息学奥赛开展情况 NOIP 报名参赛人数全国前两位。报名参赛人数全国前两位。 一等奖分数线基本前一等奖分数线基本前5 一等奖人数分配到省（山东一等奖人数分配到省（山东50左右，不包括重复获奖）左右，不包括重复获奖） NOI 全国前全国前6左右左右 金牌金牌8枚枚(4所学校所

7、学校)u全省地市学校情况：NOIP201376个一等奖分布在个一等奖分布在29个学校个学校获奖学生呈分散趋势获奖学生呈分散趋势传统成绩较好的学校，实力减弱传统成绩较好的学校，实力减弱越来越多的学校开始着手抓奥赛越来越多的学校开始着手抓奥赛 信息学奥林匹克竞赛属于信息学奥林匹克竞赛属于智力智力与应用计算机解题与应用计算机解题能力能力的的比赛，题目有相当的难度，解好这类题目，需要具备比赛，题目有相当的难度，解好这类题目，需要具备很很强的强的综合能力综合能力1.1.观察和分析问题的能力；观察和分析问题的能力；2.2.将实际问题转化为将实际问题转化为数学模型数学模型的能力；的能力；3.3.灵活地运用各

8、种灵活地运用各种算法算法的能力；的能力；4.4.熟练编写程序熟练编写程序并将其调试通过的能力；并将其调试通过的能力；5.5.根据题目的要求，自己设计测试数据，检查自己的解法是否根据题目的要求，自己设计测试数据，检查自己的解法是否正确、是否完备的能力正确、是否完备的能力 三. 考试内容 能够参加信息学竞赛的选手应该具有很强的自学能力。 需要学习有关组合数学、图论、基本算法、数据结构、人工智能搜索算法等知识 熟练高级语言和编程技巧，要具备很强的上机操作能力u要求：掌握一门计算机程序设计语言掌握一门计算机程序设计语言(怎样选择怎样选择)： Pascal C C+数据结构与算法数据结构与算法一、语言：

9、一、语言：Free pascal Free pascal （c/c+c/c+）基础）基础 二、数据结构二、数据结构 线性表、栈、队列、树、图线性表、栈、队列、树、图三、算法：三、算法： 高精度运算高精度运算 排序算法排序算法 搜索算法（搜索算法（dfsdfs，bfsbfs） 动态规划动态规划dpdp 贪心算法、模拟算法等贪心算法、模拟算法等 相关的数论知识相关的数论知识 全国联赛（NOIP）知识点：主要考察基本数据结构与算法的应用能力主要考察基本数据结构与算法的应用能力全国竞赛（NOI） 并查集、树状数组、线段树并查集、树状数组、线段树 查找树查找树 网络流网络流 几何算法几何算法主要考查建立

10、模型和算法的主要考查建立模型和算法的优化优化能力能力四. 学生的选拔与组织u信息学奥赛是一种选拔性竞赛u不是一般计算机知识的普及。 兴趣兴趣 能力能力 勤奋勤奋1.1.综合成绩突出。综合成绩突出。2.2.扎实的数学基础。扎实的数学基础。3.3.很强的自学能力。很强的自学能力。4.4.乐于和同学合作与交流。乐于和同学合作与交流。5.5.能坐得住。能坐得住。学生自身：外力：家长和班主任老师的支持家长和班主任老师的支持u人数每个年级保持在每个年级保持在15人左右较好人左右较好开始多一点，慢慢的淘汰开始多一点，慢慢的淘汰u吸引学生、培养兴趣第一堂课很重要第一堂课很重要信息学奥赛解决的问题： 经过思考能

11、够得出解决的方法，但是却很难或者根本不可能用人工的做出来。 设计算法，用计算机语言设计程序实现自己的方法，从而解决问题。步骤： 观察分析问题 思考问题，得出模型（数学模型） 设计解决问题的算法或者步骤 用计算机语言设计程序实现算法 调试验证算法的正确性 要将一张要将一张100元的大钞票，换成等值的元的大钞票，换成等值的10元、元、5元、元、2元、元、1元一张的小钞票，每次换成元一张的小钞票，每次换成40张小钞票，张小钞票，每种至少每种至少1张。张。如，有一种换法：如，有一种换法： 10元：元： 1 张张 5元：元： 5 张张 2元：元： 31 张张 1元：元： 3 张张问：一共有多少种换法。问

12、：一共有多少种换法。【举例举例1 1】换钱问题换钱问题举几个例子激发学生的学习兴趣和欲望 1010元：元： a a 张张 ( (不超过不超过1010张张) ) 5 5元：元： b b 张张 ( (不超过不超过2020张张) ) 2 2元：元： c c 张张 ( (不超过不超过5050张张) ) 1 1元：元： d d 张张 ( (不超过不超过100100张张) ) 不定方程组：不定方程组： 1010* *a+5a+5* *b+2b+2* *c+d=100c+d=100 a+b+c+d=40a+b+c+d=40 a=1;b=1;c=1;d=1a=1;b=1;c=1;d=1 问题转化为：方程组有多

13、少组正整数解？问题转化为：方程组有多少组正整数解？分析：分析：给学生代码：试运行给学生代码：试运行varvar a,b,c,d,n:longint; a,b,c,d,n:longint;beginbegin n:=0; n:=0; for a:=1 to 10 do for a:=1 to 10 do for b:=1 to 20 do for b:=1 to 20 do for c:=1 to 50 do for c:=1 to 50 do for d:=1 to 100 do for d:=1 to 100 do if (10 if (10* *a+5a+5* *b+2b+2* *c+d=

14、100)and(a+b+c+d=40)c+d=100)and(a+b+c+d=40) then n:=n+1; then n:=n+1; writeln(n); writeln(n);end.end. 换成换成50张有多少种换法？张有多少种换法？ 两张两张100的换成的换成40张，有多少种换法？张，有多少种换法？ 让学生试一试：让学生试一试：已知：已知： s=1+1/2+1/3+1/n求：使求：使s的值大于的值大于10时最小的时最小的n。【举例2 2】 求最小的求最小的n n varvar n:longint; n:longint; s:real; s:real; beginbegin s:=

15、0; s:=0; n:=0; n:=0; repeat repeat n n:=:=n+1;n+1; s s:=:=s+1/n;s+1/n; until s10; until s10; writeln(n); writeln(n); end.end.u使s的值大于10时最小的n? n=123467u使s的值大于15时最小的n? u使s的值大于30时最小的n? 知道：计算机的计算范围是有限的。知道：计算机的计算范围是有限的。 有两个无刻度标志的水杯，分别可装满有两个无刻度标志的水杯，分别可装满x x升和升和y y升的水。设升的水。设另一个水缸，可以用来向水杯灌水或从水杯向水缸里倒水，两另一个水缸

16、，可以用来向水杯灌水或从水杯向水缸里倒水，两个水杯之间也可以相互倒水。已知个水杯之间也可以相互倒水。已知x x升的水杯开始是盛满水的，升的水杯开始是盛满水的，y y升的杯子是空的，问如何通过倒水和灌水操作，用最少的步升的杯子是空的，问如何通过倒水和灌水操作，用最少的步数能在数能在y y升的杯子里量出升的杯子里量出z z升水。升水。YX水缸（足够的水水缸（足够的水,未满）未满）X=20 Y=15 Z=10 ？Y10【问题3】：倒水问题开始开始: 20 0step 1: 5 15step 2: 0 15step 3: 15 0step 4: 15 15step 5: 20 10X Y算法：广度优先

17、搜索算法：广度优先搜索数据结构：队列数据结构：队列找学生回答找学生回答复杂一点的还能吗？复杂一点的还能吗？u知识的讲解 任务驱动任务驱动 根据任务的需要讲知识点根据任务的需要讲知识点 避免使用以前大学老师的讲课方式避免使用以前大学老师的讲课方式五. 辅导进度与时间安排u三个阶段： 高一年级高一年级：（周六一个上午：（周六一个上午3个小时）个小时） 语言语言 基本算法与数据结构（基本的，不要贪多）基本算法与数据结构（基本的，不要贪多） 高一假期高一假期 专项强化训练：算法的完善和补充专项强化训练：算法的完善和补充 高二复赛考试前（高二复赛考试前（11月份）月份） 模拟训练模拟训练高一u语言部分

18、用什么讲什么 粗放型，不要面目俱到 1.三种基本结构（if for while） 2.数组 结合渗透：枚举算法；一种简单的排序算法 3.递归（自定义函数与过程）及简单应用 慢慢熟练语言（6到7个半天）u算法与数据结构： 1.深度优先搜索算法 2.广度优先搜索算法（数据结构队列） 3.简单的动态规划算法 4.树及其应用 5.图论算法 邻接矩阵存储法存数 两种最小生成树算法: 普里姆算法（prim）;克鲁斯卡尔（kruskal） 两种最短路径方法算法：弗洛伊德算法：floyed迪杰斯特拉算法：dijkstra,侧重基本知识，勿贪多，讲练结合侧重基本知识，勿贪多，讲练结合高一暑假期间（重要的集中学习时间）u算法与数据结构的补充和加深（实用性） 堆的使用 并查集 最短路径算法spfa，图的邻接表存储方法 动态规划 技巧与处理方法建议参加山东省夏令营活动建议参加山东省夏令营活动 （7月中旬下旬）月中旬下旬）学校自己训练学校自己训练u高二开学（9月份，10月份，每周两次） 10月中旬的初赛月中旬的初赛 根据具体情况，一般不需专门准备根据具体情况，一般不需专门准备 多报一部分人（参加学习是分子多报一部