2010 年 NOIP 普及组解题报告 北京市八一中学 王祺磊 感谢： 我也学习一下，现在的流行趋势，先开始感谢，但这真的是发自内心的感觉，让我发出一下这些感谢。 一、感谢和我一起并肩战斗信息学奥赛教学一线的老师们，是你们给了我温暖，让我感受到一个温馨的集体，在其中，我们一起学习，一起研讨； 二、感谢一直和我一起战斗在一起的孩子们，是你们跟我一起，在风雨中奋斗，一起成长； 三、感谢我的几位师长，是你们一直在我成长的过程中，指引我前进的方向； 四、特别感谢，几位与我一起成长起来的“小牛”，是你们，反馈给了我很多需要学习的知识，让我逐渐成熟。 关于 2010 年普及组考题： 没有想到，这次的题目和2008、2009 年的题目完全风格两样，我不知道是不是出题老师发生了变化。但是，总体感觉，题目趋于容易，甚至没有涉及 DP、搜索中的初级方法。但是，题目很多知识点又隐含颇多。不容易拿到完美的分数。感谢出题老师，给我们带来的这届优秀题目。 题目分析： 一、数字统计 此题，曾经在某 OJ 上看到过原题。要求和实现都非常简单。无非是，枚举出所有在范围内的数字，然后对数字进行拆分，对每一位数字进行判断。 一个朴素的for 循环，嵌套一个while 循环，就可以解决这道题目。 下面是程序的核心部分： for ( i = l ; i <= r ; i++ ) { t = i; while (t > 0) { y = t % 10; if (y == 2) s++; t /= 10; } } 此题丢分，绝对可以认为是绝不应该出现的事情。往参赛选手能够更加注意自己的程序细节，避免问题出现。 二、接水问题 问题描述隐晦，引导学生朝着纯枚举的思想前进，部分用秒枚举的学生会导致严重超时。但题目的核心思想却应该是模拟问题发生的本质顺序。也就是，每个新加入的人去接水的位置，一定是当前数列中和最小的那列。所以实现的方法，就是每个新数字，进入前，找出当前序列中最小的位置，加入进去。直到所有的数字都加入进去后结束。最终从所有的数字中，找出最大的那个值，即为所求。 但是，其实有更合适的模型——插入法排序。 即从大到小排序后，无非就是把数字加入到最后一个数值之上，然后运用插入法排序原理，把这个新数插入到合适位置。最终输出的是数组的最大值即可。 下面是程序的核心部分： 首先，对前 m 个数进行排序，然后后面的 n – m 个数，就需要模拟插入了： for (i = m ; i < n ; i++ ) { cin >> t; t...
