都在说小升初中信息学越来越重要，信息学到底是个啥
都在说小升初中信息学越来越重要，信息学到底是个啥
题记：泽哥认真学习了一下信息学的相关内容。
备注：由于已经没有那么“专业”，这篇文写了好久。
要真说起来，“信息学”才是泽哥的本家，毕竟泽哥大学的就读学院叫：信息科学与技术学院。只不过刷了一年POJ（好像是这个）后，觉得自己可能不是这块料（谁知道十年后会这么火），最后转型教了数学。所以当得知最近信息学如此之火的时候，泽哥特别去了解了一下小学的信息学和大学所在院名里的信息是不是一个“信息”。
以下所有题目及题目分析均来自“小猴编程”发布的“2019年北京各区青少年信息学科普活动解析报告“（可点击查看详细内容）。其他内容来自泽哥从小升初方面得出的分析。
信息学目前小学都有哪些考试？
规模最大的应该算是原来的NOIP(全国青少年信息学奥林匹克联赛)系列赛事了，今年改名叫CSP(计算机软件能力认证)非专业级别，原来小学生可以报名NOIP普及组，对应现在的CSP-J，对标的是初中省级联赛；今年改名之后小学生连CSP-S都可以报名了，不过CSP-S对标的是高中省级联赛，小学生虽然能报名，但是基本上不可能取得较好成绩的。
原NOIP系列赛事是信息学最重要的竞赛，主要有三个重要作用：1.NOIP系列赛事由科协下属的CCF(中国计算机协会)主办，已经举办24届了，是被公认非常专业的赛事，可以切实有效的起到检测学习效果，评定学习能力的作用；2.NOIP提高组的成绩一直都是选拔NOI(国家级决赛)参赛选手的重要依据，参加NOI就有机会进入国家集训队保送各重点大学甚至参加IOI(国际级)；3.NOIP提高组一等奖可以获取绝大部分重点大学自招资格。
今年NOIP改名CSP后，目前可以确定第1和第2个作用已经由CSP继承了，CSP是否还能继承原NOIP的第3个作用还有待明年看各大学的自招情况决定，但是基本上继承了第1和第2个作用的CSP是最有可能得到各重点大学承认的赛事。
除了CSP外，大多数孩子会接触到的一般是北京市科协举办的信息学市赛和各区科协举办的信息学区赛；2019年以前只有市赛，直接报名即可参加，2019年是第一年举办各区区赛，而且形成了区赛选拔，市赛决赛的机制，这也从某种程度上可以看出信息学的重要性越来越大，信息学学科发展也开始加速。而且很多区的这个比赛都是依托于某些学校来进行的。
信息学目前在小升初中的作用到底有多大？
首先，信息学作为在2019年4月10日教育部办公厅钦点的小学生能参加的仅存的学科类竞赛，至少给了大家一个能在简历中添砖加瓦的途径。而且科协现在搞的各种比赛越来越多（之前有学校举办中学科协的活动还被误认为是小升初活动），说不定被学校重视的可能性越来越大。
但是，说实话，信息学要达到奥数曾经的作用在短时间内基本上是不太可能。奥数能有今天的地位，完全是因为RDF（校名）LLL（人名）当年小升初招的那一批奥数好的孩子高考毕业时全清北闯出的名声，后来各个学校发现原来小升初选奥数好的孩子高考成绩这么好，就掀起了靠奥数升学的热潮。但是信息学目前还没发现有这个趋势（小乖不算，他那是双修）。
但是即便如此，至少从近两年看，海淀和朝阳的部分学校对于信息学这块也是越来越重视，至少在很多学校活动中有“信息学”的字眼出现，也穿插了一些和信息学思维方式相关的题目。
说了这么多学信息学到底有什么用？
信息学最大的作用其实是提前为高考自招做准备，信息学作为高中五大联赛之一，目前来看是学的人最少的联赛，也是相对入坑早比较容易出成绩的学科。毕竟我们做了这么多，出口都是在高考，作为学校也是一样的考虑，能招到一些未来能够获得高考自招资格的孩子对于学校也是非常有帮助的。
从非功利的角度来看，这个社会对编程的需求越来越大，感觉这个在五大联赛中最不被重视的联赛再过几年就要跻身第二了啊。赶紧趁着小学学业还没那么重的时候赶紧多学学吧。
题目大概长成什么样子？（特别提示文末有彩蛋）
以海淀区为例，一共2个小时的比赛，共6道题目，涉及C++基本语法和简单的算法涉及。需要孩子有对应的数学基础，以及语法、程序执行逻辑等基本功，如果要冲刺高分，还需要会枚举、贪心、搜索等简单的算法设计。
比如海淀区的第一题：枚举
【题目描述】
对于给定的数n，除了n本身外，最大的约数是多少？
【输入说明】
共一行，包含一个整数n
【输出说明】
共一行，包含一个整数，表示n除了自身以外的最大约数
样例和数据范围已省略
比如海淀区的第六题：盒子（box）
源代码：box.cpp
输入文件：box.in
输出文件：box.out
时间限制：1s
空间限制：512MB
【题目描述】
小D在玩堆盒子的游戏，每个盒子有一个强度，代表它上方最多能堆多少个盒子。由于盒子都是一样大的，所以不能在一个盒子上并列放超过一个盒子。
现在小D有n个盒子，第i个盒子的强度为Xi，小D想知道，如果他要把这些盒子全部堆起来，至少要堆多少堆。
【输入说明】
从文件box.in读入
第一行读入一个整数n，代表小D有的盒子个数
第二行读入n个整数，第i个整数Xi表示第i个盒子的强度
【输出说明】
输出到文件box.out
共一行，一个整数表示小D至少要堆多少堆
【样例输入】
5
0 2 1 1 2
【样例输出】
2
【数据范围】
对于20%的数据，0～10
对于50%的数据，n小于等于1000
对于100%的数据，n小于等于500,000，Xi小于等于1,000,000,000
题目大致思路是啥（特别提示文末有彩蛋）
第一题：枚举
解题思路
如果不考虑n的数据范围，只要逐一枚举n-1到1之间的所有数，找到其中n的最大约数即可。按官方数据，这一做法可以获得60%的分数。
可以想到，如果d是n的约数，且d要尽量大，那么n/d就要尽量小。我们用d’表示n/d，并从2、3、4、……、
中寻找n的最小约数d’，如果能找到，答案就是n/d’；如果找不到，答案就是1。这里
最大为44721，枚举一遍的时间效率，已经足够拿到满分。
注意点
记得处理n本身是质数的情况，此时的答案是1。
第六题：盒子
解题思路
可以发现，在箱子的叠放过程中，强度大的箱子应该尽量往低处放，强度小的箱子应该尽量往高处放。为此，首先应对所有箱子按强度大小做排序，接着可以按强度从小到大的顺序考虑箱子的摆放。
初始时，只有强度最小的箱子，它单独成为一堆。之后考虑每一个箱子时，可以先尝试把它放到第1堆的末尾，如果不合法，就依次尝试将它放到第2、3、4……堆的末尾，直至找到第一个合适的位置。如果所有箱子堆的末尾都无法放下这一个箱子，就将他单独成为一堆。具体实现时，为快速判断一个箱子是否可以放到某一堆箱子的末尾，可以在贪心的过程中，顺便维护每一堆箱子的已有箱子数。在此基础上，只需判断相应的箱子数是否不超过当前要摆放的箱子的强度即可。
上述算法的整体时间效率，取决于一开始的排序，以及后续的贪心。其中，贪心算法的时间效率关键是看最终的箱子堆数。根据官方数据，如排序算法采用冒泡排序、选择排序或插入排序等
算法，本题可以拿到50%的分数；如采用
排序算法，或使用C++ STL算法中的sort()，虽然整体算法的时间效率最坏情况仍旧是
，但本题已经可以拿到满分。
算法优化1
可以发现，在上述贪心算法中，第1堆箱子、第2堆箱子，直至最后一堆箱子的箱子数，将始终保持成一个非上升的单调序列。因此，在寻找当前箱子所能堆放的第一个合适位置时，可以采用二分法替代枚举法。此时，本题的整体时间效率为
，即便加强测试数据，也可以获得满分。
注意点
1、排序算法在比赛中十分常见，建议熟练掌握C++ STL算法中的sort()，并注意相应的参数取值；
2、本题的读入数据量较大，如要争取满分，建议通过逐字符读入来获取数据。
