NOI走向的思考

信息学竞赛展望全国青少年信息学奥林匹克竞赛（NOI）是由中国计算机学会主办的一项面向全国青少年的信息学竞赛和普及活动。

也是与联合国教科文组织提倡的国际信息学奥林匹克竞赛，同步进行的一项竞赛活动。

信息学竞赛分为省赛（NOIP）、国家赛（NOI）、中国代表队选拔赛暨全国信息学精英赛（CTSC）、亚洲赛（APIO）、国际赛（IOI）等比赛。

其中NOI是省级代表队最高水平的大赛。

NOIP是全国青少年信息学奥林匹克联赛，分初赛和复赛两个阶段：初赛考察实用的计算机普及科学知识，笔试。

复赛为程序设计，须在计算机上调试完成。

CTSC是决定中国代表队人选决定的最重要比赛，选出高素质的信息学人才参加IOI。

APIO 是亚洲与太平洋地区信息学奥赛，该竞赛是亚洲和太平洋地区每年一度的国际性赛事。

IOI是出国参加国际信息学奥林匹克竞赛。

由中国计算机学会组织代表队，每年一次代表中国参加。

奥赛的宗旨是向那些在中学阶段学习的青少年普及计算机科学知识；给有才华的学生提供相互交流学习的机会；通过竞赛及相关活动培养优秀的计算机人才。

为了给的确有兴趣、有潜力的学生进行科学研究和实践提供一个更加公开、严谨、洁净的竞争平台，更好地促进学生身心健康发展，国家对现行竞赛保送加分政策做出了相应调整和完善，自高中2011级开始实行。

第一，奥赛全国决赛获奖学生，调整为高校可在同等条件下优先给予参加本校自主选拔录取考核的资格，是否可享受加分照顾由生源所在地省级招委决定，不再具备保送资格。

第二，对奥赛省赛区一等奖获奖学生，调整为高校可在同等条件下优先给予参加本校自主选拔录取考核的资格，不再具备保送、加分资格。

第三，对获得奥赛全国决赛一等奖并被中国科学技术协会遴选为参加国际奥赛国家集训队的学生，仍给予保送资格。

奥赛获奖与高考保送脱钩，旨在防止奥赛和功利性结合的太紧，这看似减少了机会，其实不然，清华、北大等一流名牌大学对信息学竞赛获奖者依旧非常青睐，这种热情不会因为高考取消保送而减少。

反思
1.题目看仔细，注意细节和陷阱，细节要考虑到位。

一般而言样例
都比较水，可以出一些临近边界的数据，多测试几遍。

2.在读完题目后，不要着急写程序，应先思考算法的正确性，并想
一下易误之处，不要遗漏。

3.文件名、输入输出别打错，最好用in文件试一下能不能生成out
文件，在最后检查一遍有没有将输入输出注释。

4.要计算程序的时间，空间复杂度，不能爆内存。

写完程序之后注
意边界数据，看看是否会爆数组。

5.在不确定算法是否正确时，可以写一个暴力算法，进行对拍。

6.做找规律题时可以先用暴力，找到规律之后在做。

实在做不出来
是可以打表或暴力。

注意数据特别大时很有可能找规律。

7.遇到特别难的题目可以放弃，直接用暴力。

节约的时间来检查前
面的题目，尽量保证能得到的分不能丢。

8.要注意做题顺序，做题前先看一遍所有题目，防止出现题目不是
按照难度排序，导致死磕难题，时间不够的现象。

9.要注意变量的范围，赋值时不能超出范围。

需要mod一个数时，
没改变一次结果都要mod一次。

10.S tring 在读入时尽量不要用cin，cin速度太慢，可以先用scanf读
入一个char*，再转换成string。

如果一定要用，要先关闭同步。

信息学奥赛分区联赛复赛经验漫谈一、认真审题审题对于信息学竞赛来说尤其重要。

同一个题目如果数据限制差异大的话，可能难度差异也很不同。

例如：输入A,B,输出A+B的值。

如果题目说0<=A,B<=10000,这道题目无疑是一道很简单的题目，但如果题目说0<=A,B<=10000000000000000000000000000000000000000000000显然就要用到高精度数的处理了。

从某种意义上说，数据限制也暗示了你可能的算法。

数据小，也许是搜索派上用场的时候，数据大了，可能只能考虑动态规划，数学方法等高效的算法了。

二、编码和调试的能力复赛考查的算法并不困难，选手在实现上的问题往往还要大一些。

建议大家：一，充分利用草稿纸，不要对自己的“心算能力”太自信了。

编程熟练的同学喜欢“一气呵成”，拿到题目就开始编码。

我认为这样不好。

做信息学竞赛竞赛题的思维过程是丰富而曲折多变的，考虑问题必须全面。

仅凭一时的“感觉”来编程往往是漏洞百出。

初学者常常忘记做一些初始化工作（远不止变量赋初值这种最简单的），即使有经验的同学也难免因一时疏忽写出几个错误的语句。

最要命的是“第一感觉”的算法是错误的或者效率太低，而程序编了大半才发现...做一些复杂的题目（以前复赛的题目其实没有特别复杂的，但今后可说不准），大多数人多会在一分心的时候突然短了思路，不知道下一步该写什么了。

二，编码采取自顶向下，逐步求精的方法，调试时采用输出中间结果的办法及时找出错误的地方。

可以这么说，思路越清晰，对自己程序的算法和编码越了解，调试也会越顺利（一定不要忽视）。

三、最大限度的发挥自己的水平看上去是废话，但必须说，当临近比赛的时候，这一点绝对比提高自己的编程能力重要和实际的多。

下面我谈谈从这几届分区联赛中得到的一些启示。

1.正确的估计题目的难度和自己的水平初学者常常“意气用事”，拿到一道看起来很“爽”的题目就开始做了，其实这样不好。

关于信息学奥赛与数学学习相互促进关系的几点思考作者：刘彧麟来源：《中国校外教育(下旬)》2017年第10期【摘要】在对信息学奥赛与数学学习的认知分析基础上，通过对信息学奥赛和数学学习所要求核心素养的研究，提出了数学学习为信息学奥赛奠定基础、信息学奥赛是数学学习有益补充和信息学奥赛拓展了数学学习空间的几点思考。

研究表明，信息学奥赛与数学学习是相辅相成的，通过信息学奥赛不仅训练思维、提升信息素养，还能融通与数学学习的联系。

【关键词】信息学奥赛数学学习信息素养相互促进一、前言最开始接触信息学竞赛和编程是小学五年级，是一个名叫“小学生程序设计竞赛”的校内兴趣班，语言用的是Pascal。

作为小学生，Pascal语言的命令含义太复杂，很难理解，指导老师就让我们死记硬背，虽不知道含义，但现在我都能记得一些关键字，如“u-s-e-s”，“v-a-r”，等等。

之后的小学六年级和初中三年我参加了数学竞赛，信息学竞赛没有再接触，由于从数学竞赛获益良多，让我坚信参加竞赛能促进数学学习的提高，所以中考录取后我参加了成都七中的暑期夏令营，我是冲着数学竞赛班去的，但大、小两轮夏令营选拔之后（新生夏令营，基础学科青年英才培养夏令营），最后进入的却是信息学竞赛班，初期我还有些抵触，但经过近一年的训练后，却深刻的感受到信息学竞赛对思维模式和数学学习，乃至对现在这个信息时代的理解都有很大的促进作用，这里结合自己的体会，谈谈我的几点思考。

二、信息学奥赛之我见数、理、化、生物和信息学奥赛被称为中国高中的五大竞赛，由于获奖对拓展学生的思维和升学都有益，故受到了学校、学生和家长的广泛重视。

一般的说法是，按照大学对不同竞赛成绩的认可度，五大竞赛含金量排序是：数学物理最高，化学次之，信息学和生物相对低一些。

特别是信息学，由于高考不考信息学，如果最后不能得奖，那么“挂了你就真的就挂了”，因此，在选择竞赛科目的时候，我们常常会听到“别选信息学”的建议，然而通过一年系统的信息学奥赛培训和学习，我并不认可这一观点。

信息学奥赛的实践与体会信息学奥林匹克竞赛是一项益智性的竞赛活动，核心是考查参赛选手的智力和使用计算机编程解题的能力。

信息学奥林匹克竞赛要求参赛选手有如下能力：针对竞赛题目中的要求构建数学模型，构造出有效的算法和选用相应的数据结构，写出高级语言程序，上机调试通过。

现从我自己近几年来信息学辅导教学实践经验和教学工作收获出发谈谈体会。

信息学奥林匹克竞赛是一项旨在推动计算机普及的学科竞赛活动，重在培养学生能力，使得有潜质有才华的学生在竞赛活动中锻炼和发展，提高他们创造性地运用程序设计知识解决实际问题的能力。

我是2001年参加工作，从2005年开始从事信息学奥林匹克竞赛的指导工作。

2009年辅导学生获提高组一等奖，并入选省队。

目前信息学奥林匹克竞赛在我们学校正广泛开展，学生也表现出非常高的热情。

作为一名信息学奥林匹克竞赛辅导老师，我根据近几年来的教学实践经验和教学工作收获出发谈谈自己的体会。

一、提高教练自身的素质学生所学习的内容是程序设计与数据结构，要求我们教师不仅懂一种程序设计语言而且还要精通。

2005年我开始从事信息学奥林匹克竞赛辅导工作的时候发现，大学所学的程序设计所编的程序难度根本没有奥林匹克竞赛所编的程序难度高。

给学生一杯水，要求教师有一桶水。

所以我就买了许多关于信息学奥林匹克竞赛的书，自己好好的专研起来，提高自身的专业素质。

现在我给学生辅导的题目，无论简单的还是难的题目，每一道题都要求自己在给学生上课前亲自做一遍。

同一道题目有不同的解法，作为教师要好好比较。

如果你没有过硬的专业知识，辅导学生，那就会误人子弟了。

同时信息学和其他学科相比有其特殊性，因为信息学的知识会“过期”，所以信息学的学习不得不“与时俱进”。

因此作为一名信息学奥林匹克竞赛辅导教师，只有具备终身学习的态度和能力，才能跟得上信息学的发展。

二、运用有效的教学方法信息学奥赛的内容主要是程序设计与数据结构，这些全部都是大学计算机本科专业的重点课程。

关于信息学竞赛的个⼈看法与建议关于信息学竞赛的个⼈看法与建议　本⼈是个信息学奥赛的蒟蒻，在初⼆才开始学习信息学奥赛，但是毕竟是福建的OIer,对福建的信息学竞赛有⼀定的了解，在这⾥给出⾃⼰对于信息学竞赛的个⼈看法与建议。

先列出信息学奥赛的流程（括号内为⽉份）NOIP初赛（10）-->NOIP复赛（11) -->福建省选拔赛（4、5）--> （亚太信息联赛APIO等分赛事）-->NOI(7) -->国家队选拔赛（5）-->IOI（8）1、NOIP初赛：每年10⽉举办，笔试，选取⼤概20%--30%的⼈进⼊复赛（2019年增加后全省进⼊复赛⼈数改为1000⼈)2、NOIP复赛：每年11⽉举办，上机，全省集中在⼀个市各考点进⾏考试，普及组3.5⼩时4题，提⾼组两天7⼩时6题。

NOIP拿到省⼀等奖是所有的基础，拿到这个奖项就有了各个学校⾃主招⽣的资格（仅为资格），如果没有这个奖项，后⾯列出的所有信息竞赛均⽆资格参加。

福建的省⼀等奖得奖分数线是不低的，如图。

在省⼀的获奖选⼿前50+中，会进⼊省集训队。

3、福建省选拔赛：福建省选拔赛会选出福建信息省队选⼿（全省⼤概10~15⼈），⼈数分为普通（A类），奖励⼈数（B类）（根据上⼀年NOI情况确定⼈数）。

福建信息省队⾮常强⼤，进⼊后许多⾼校⾃招都将向你抛出橄榄枝。

进⼊省队后才有资格参加后⾯赛事。

4、NOINOI是所有⼤神选⼿的竞技场，福建历来获奖率很⾼，NOI将选出50名左右进⼊国家集训队（不是国家代表队）。

若你拿到NOI⼀等奖，你将拥有很多⾼校的⾼降分优惠，若进⼊国家集训队，清北都将给予你⾃招⾼降分甚⾄⽆条件录取。

5、国家队选拔赛国家队选拔赛将经过多轮测试，从50名国家集训队⼈选中选出4名国家代表队，他们将代表中国参加IOI（世界信息学奥林匹克竞赛），若你进⼊国家代表队，所有⾼校⽆条件录取是绝对ok的。

6、IOI世界最顶尖⽔平的竞赛，你的成绩将为国添荣，若你达到这个层次，已经不需要任何⼈的指导了。

信息学竞赛辅导微得------ NOIP复赛归来反思今年11月份，我带学生参加了NOIP2011普及组复赛，竞赛的结果虽有所突破，但与一些信息学竞赛传统强校还有一定差距。

虽然今年竞赛试题难度较去年比加大了，但其实我们不是没有一点希望获得更大突破的，从这几年的情况来看，如果我们再努力一些，再多做一些练习，再与外市多交流一些，还是有可能实现更大突破的。

像合肥、芜湖等市都有较大突破的情况下，而我们学校还处于较落后的水平。

这与整个安庆市的信息学竞赛水平有很大关系，也跟学校的重视程度有关系。

我市没有多少学校参加信息学竞赛，即使我校重视开展信息学竞赛，也仅仅停留在与本市其它信息学重点强校的较量上，并不太关心在全省内的水平。

我们要在全省的比赛上有所突破，能够拿牌，不再做看客，我们还有很多路要走，我从以下几个方面来谈谈我这次复赛回来对竞赛辅导的一些看法，也希望各们老师帮助我共同献计献策，共同把信息学竞赛搞好。

一、时间时间对任何一项竞技比赛都是无比重要的，在信息学竞赛中也毋庸置疑。

要想获得更好的成绩，比别人更优秀，只有付出更多的时间，并且更好的利用时间。

我们现在的时间安排是每周辅导半天。

这对竞赛的要求来说，是远远不够的，但目前也没什么太好的办法。

因为是周末搞竞赛辅导，占用了学生的休息时间，因此也流失了一部分优秀学生（许多学生还有或多或少其他课程的课外辅导），但这也是没办法的事情，我们只有在夹缝中生存。

初一学生从九月开学，到NOIP初赛的时间仅仅有一个半月，要想在初赛中取得好成绩，必须完成pascal程序设计语言的学习，以及基本算法及数据结构的学习，这个强度是相当大的，这不仅要有学生的聪明才智，还要有充足的时间做保障，两者缺一不可。

而对于NOIP复赛来说，难度更大，所学知识都是大学以上的内容，需要准备的时间要长得多，至少１年以上。

所以，我认为一定要开展好初一的信息学竞赛培训。

初一把苗子选好，到初二时，经过长期的集训，争取能拿到加分。

一、（搜索）双向广度搜索广度搜索虽然可以得到最优解，但是其空间消耗增长太快。

但如果从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。

范例：有N个黑白棋子排成一派，中间任意两个位置有两个连续的空格。

每次空格可以与序列中的某两个棋子交换位置，且两子的次序不变。

要求出入长度为length的一个初始状态和一个目标状态，求出最少的转化步数。

问题分析：该题要求求出最少的转化步数，但如果直接使用广度搜索，很容易产生数据溢出。

但如果从初始状态和目标状态两个方向同时进行扩展，如果两棵解答树在某个节点第一次发生重合，则该节点所连接的两条路径所拼成的路径就是最优解。

对广度搜索算法的改进：１。

添加一张节点表，作为反向扩展表。

２。

在while循环体中在正向扩展代码后加入反向扩展代码，其扩展过程不能与正向过程共享一个for循环。

３。

在正向扩展出一个节点后，需在反向表中查找是否有重合节点。

反向扩展时与之相同。

对双向广度搜索算法的改进：略微修改一下控制结构，每次while循环时只扩展正反两个方向中节点数目较少的一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数，加快搜索速度。

二、（搜索）分支定界分支定界实际上是A*算法的一种雏形，其对于每个扩展出来的节点给出一个预期值，如果这个预期值不如当前已经搜索出来的结果好的话，则将这个节点(包括其子节点)从解答树中删去，从而达到加快搜索速度的目的。

范例：在一个商店中购物，设第I种商品的价格为Ci。

但商店提供一种折扣，即给出一组商品的组合，如果一次性购买了这一组商品，则可以享受较优惠的价格。

现在给出一张购买清单和商店所提供的折扣清单，要求利用这些折扣，使所付款最少。

问题分析：显然，折扣使用的顺序与最终结果无关，所以可以先将所有的折扣按折扣率从大到小排序，然后采用回溯法的控制结构，对每个折扣从其最大可能使用次数向零递减搜索，设A为以打完折扣后优惠的价格，C为当前未打折扣的商品零售价之和，则其预期值为A+a*C，其中a为下一个折扣的折扣率。