G2019信息竞赛第三次考试解析：接苹果游戏、漂亮值与正方形个数

"本次竞赛主要涉及三道编程题目，分别是接苹果游戏、漂亮值计算和正方形的个数统计。" 1. 接苹果游戏 (apple) 这是一个动态规划问题，目标是计算控制小船接住所有苹果所需的最小移动距离。游戏规则如下： - 屏幕分为N列，小船初始位于最左边的M列。 - 苹果从屏幕顶部依次落下，只有当前苹果落地后，下一个才会开始落下。 - 小船可以在屏幕内左右移动，但不能移出屏幕。 - 需要找到一个策略，使得小船在接住所有苹果时，移动距离最小。 解题思路： - 可以使用动态规划，定义状态dp[i][j]表示吃到第i个苹果时，小船在第j列所需的最小移动距离。 - 通过转移方程更新状态，例如dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1]) + 1，表示小船在当前位置、左移或右移接到第i个苹果的距离。 - 最终输出dp[J]中的最小值，即为答案。 2. 漂亮值 (beauty) 这是一道矩阵操作题，要求找出矩阵中最漂亮的正方形区域，计算其漂亮值（主对角线之和减去副对角线之和）。 - 矩阵大小为N×N，每个元素为整数，范围在[-1000,1000]。 - 最漂亮的正方形区域是漂亮值最大的那个。 解题方法： - 可以采用滑动窗口的方法，遍历矩阵的每个元素作为左上角，计算对应正方形的漂亮值。 - 用两个变量分别记录主对角线和副对角线的和，更新最大漂亮值。 - 最终输出最大漂亮值即可。 3. 正方形的个数 (square) 该题考察的是在二进制矩阵中统计全为1的正方形子矩阵的数量，正方形边长至少为2，可以重叠。 - 给定一个N×N的矩阵，其中元素为0或1。 - 要求计算不同边长的全1正方形子矩阵的数量。 解题策略： - 对于每个边长l，可以使用双重循环遍历所有可能的左上角位置。 - 在每个位置，检查以该点为左上角的l×l矩阵是否全为1，如果是，则计数加1。 - 输出每个边长l对应的全1正方形数量。 这三道题目涵盖了动态规划、矩阵操作和二进制矩阵处理等计算机科学基础算法，对于提升编程能力与算法理解有着很好的实践价值。