noip 2010普及组解题报告

### NOIP 2010普及组解题报告解析 #### 一、概述 NOIP 2010普及组的解题报告由北京市八一中学的王祺磊老师撰写，该报告对当年的比赛题目进行了深入浅出的解析。王祺磊老师在报告中不仅表达了对同行教师、学生们以及几位特别帮助他的“小牛”的感激之情，还针对比赛中的三道题目——数字统计、接水问题、导弹拦截——进行了详细的解答。 #### 二、数字统计 **题目概述**：此题要求统计在给定区间内所有数字中包含数字2的个数。 **解题思路**： - 枚举区间内的每一个数字，并将每个数字分解成其各个位上的数字。 - 对于每一个位上的数字，判断是否等于2，如果是，则计数器加一。 **程序实现**： ```cpp for (i = l; i <= r; i++) { t = i; while (t > 0) { y = t % 10; if (y == 2) s++; t /= 10; } } ``` **注意事项**：此类题目相对简单，但需要注意边界条件的处理，以及循环中变量的更新逻辑。 #### 三、接水问题 **题目概述**：这是一道模拟类题目，要求根据给定的排队情况计算出最长等待时间。 **解题思路**： - 核心思想在于模拟每个人加入队伍的过程，并且每次新加入的人总是站在当前队伍中等待时间最短的那个位置后面。 - 另一种更优的实现方法是采用插入排序的思想，即对于新加入的人，将其插入到已排序的队列中适当的位置。 **程序实现**： 1. 首先对初始的m个人的等待时间进行排序。 2. 对于剩下的n-m个人，模拟其加入队伍的过程，并更新等待时间。 3. 输出最终队列中等待时间最长的人的时间作为答案。 ```cpp // 对前m个数进行排序 // 接下来模拟剩余n-m个人加入队列的过程 for (i = m; i < n; i++) { cin >> t; t += a[m - 1]; // 当前人加入队列后的等待时间 j = m - 1; // 找到合适的位置插入当前人 while (j > 0 && a[j - 1] < t) { a[j] = a[j - 1]; j--; } a[j] = t; } // 最终a[0]即为等待时间最长的人的时间 ``` **技巧总结**：本题通过模拟和插入排序的方法解决了问题，体现了模拟算法和排序算法的应用场景。 #### 四、导弹拦截 **题目概述**：导弹拦截题目涉及多个目标的动态调整，要求在满足特定条件的情况下，优化两个拦截区的半径。 **解题思路**： - 使用贪心算法结合枚举策略来解决问题。 - 将所有目标按照到第一个拦截区中心的距离平方进行排序。 - 依次考虑每个目标，更新两个拦截区的半径。 **程序实现**： 1. 定义结构体存储目标的位置信息及其与两个拦截区中心的距离平方。 2. 使用快速排序对目标进行排序。 3. 逐步更新两个拦截区的半径，并记录最小的半径平方值。 ```cpp // 结构体定义 struct dian { int x, y, j1r, j2r; } d[100050]; // 快速排序 void qsort(int s, int e) { dian t; int l, r; if (s >= e) return; l = s; r = e; t = d[s]; while (l < r) { while (l < r && d[r].j1r >= t.j1r) r--; d[l] = d[r]; while (l < r && d[l].j1r <= t.j1r) l++; d[r] = d[l]; } d[r] = t; qsort(s, r - 1); qsort(r + 1, e); } // 更新半径的过程 r = d[n].j1r; // 初始化半径 for (i = 1; i < n; i++) { // 更新第二个拦截区的半径 // 继续后续逻辑 } ``` **技巧总结**：通过排序和贪心策略，有效地解决了动态调整半径的问题。 ### 结论 通过对以上三个题目的解析可以看出，NOIP 2010普及组的题目虽然在表面上看起来较为基础，但在实际操作中需要考生具备良好的编程习惯和严谨的逻辑思维能力。特别是对于细节的把握、数据结构的选择以及算法的设计等方面都有较高的要求。此外，从王祺磊老师的解题报告中也可以看出，教师与学生之间的相互学习是非常重要的，这对于提高教学质量和学生能力都有着积极的意义。