“科大国创杯”2023 年安徽省青少年信息学科普日活动 ACSP-J 组

【“科大国创杯”2023 年安徽省青少年信息学科普日活动 ACSP-J 组】是一个针对初中生的编程竞赛，旨在提升青少年的信息技术能力，特别是算法设计和问题解决技巧。以下是对活动中涉及的三个算法问题的详细解析： 1. **评分 (score)**： 这个问题是关于如何计算参赛选手的平均得分。问题要求去除每个选手的最高分和最低分后计算平均值。由于评委数量固定，可以先计算所有得分的总和，然后去掉最大和最小得分，最后除以评委人数得到平均分。时间复杂度为O(nm + n log n)，其中n是选手数量，m是评委数量。 2. **数数 (count)** 题目涉及到组合数学和双指针技巧。给定一组木棍长度，目标是找出两根较短的木棍和一根最长的木棍，使得这三根木棍可以拼接成一个三角形。首先对木棍长度进行排序，然后使用双指针方法枚举较短的两根木棍，同时维护最长木棍的可能范围。时间复杂度为O(n^2)。 3. **行走 (walk)** 此题是一个图论问题，要求在每次删除一条边后找到从(1, 1)到(n, n)的最短路径。可以先求出原始网格图的最短路径，如果删除的边不在最短路径上，则路径长度不变。如果删除的边在路径上，可以考虑将网格划分为若干条斜线，每条斜线上点的x+y值相同。对于每条路径，可以找到所有其他与被删除边相邻的边来替代它。时间复杂度为O(n^2 + q)，其中q是询问的数量。 4. **石子 (stone)** 这是一个涉及贪心策略和区间合并的问题。在给定区间[l, r]内，需要找到最小的合并代价。当l=r时，问题简化为处理单个点。贪心策略是考虑最小值的位置，如果最小值在已合并区间的左侧或右侧，会优先合并。如果最小值既不在左侧也不在右侧，可以将最小值及其右侧连续的点视为一个新点。然后，通过比较这些合并点的合并代价来确定合并顺序。可以使用两个栈分别处理初始点左右两侧的点，栈内的元素按照合并代价递增排序。每次选取代价较小的点进行合并，最终实现O(n log n)的时间复杂度。 这些题目覆盖了算法中的基础概念，如模拟、排序、双指针、最短路径、区间合并等，都是编程竞赛和信息技术教育中常见的问题类型。通过这样的活动，参与者可以锻炼逻辑思维，提高解决问题的能力。