试题讲解

华中农业大学出题组

华中农业大学第十五届程序设计竞赛（新生赛）

2025年12月7日

L. 山海之约

题目大意

给定 $a, b$ ，判断 $a + b = 350234$ 是否成立。

注意每个测试点有多组测试数据，直接判断即可。

I. 学霸题

题目大意
给定三个点 $A, B, C$ ，找出一个点 $D$ 使得这 4 个点可以连成一个平行四边形。

不妨设平行四边形即为平行四边形 $ABCD$ 。对于互不重合的点 $A, B, C, D$ ，四边形 $ABCD$ 为平行四边形的充要条件为 $AB = CD$ 。
这等价于 $(x_D - x_C, y_D - y_C) = (x_B - x_A, y_B - y_A)$ 。
取 $(x_D, y_D) = (x_C + x_B - x_A, y_C + y_B - y_A)$ 即可。

H. 对决

题目大意

给定两个字符串，计算特定子串的出现次数。

注意到子串的长度不超过 5，采用朴素的 $O(nm)$ 的字符串匹配方式即可。

B. 爱的魔法

题目大意

给定一个序列，对于序列中的每一个数，交换至多两个数位。最大化操作后的序列和。

首先，每一个数能取到的最大值是相互独立的。我们只需要求每一个数操作后的最大值。
由于数的数位不超过 6 位，所以对于每一个数，枚举交换的数位取最大结果即可。

A. 矩阵游戏

题目大意

给定一个单调不降的序列 $[b_1, b_2, \ldots, b_n]$ ，矩阵 $A$ 由序列 $\{b\}$ 复制 $k$ 行组成。签到哥位于 $(i, j)$ 时可以移动到 $(i+1, j-1)$ 或 $(i+1, j)$ 或 $(i+1, j+1)$ 。签到哥只能前往值比当前体力小的位置，签到哥移动后体力会相应增加。

由于序列 $\{b\}$ 单调不降，所以相比于移动到 $(i+1, j)$ ，移动到 $(i+1, j-1)$ 的选择一定更不优；
当签到哥可以移动到 $(i+1, j+1)$ 时，移动到 $(i+1, j)$ 的选择一定更不优。
朴素实现上述过程的时间复杂度是 $O(Tk)$ 的。
实际上，从 $(i, j)$ 走到 $(i + 1, j)$ 的操作是重复的。当当前体力为 $x$ ，下一列的值与当前体力的差为 $y$ 时，签到哥还需要在当前列走 $\left\lceil \frac{y}{x} \right\rceil$ 次才可以移动到下一列。
按照上述过程模拟即可。时间复杂度 $O(n)$

M. 终极考验

题目大意

给定 $n$ 个石柱的高度。每次操作可以选择一个 $i$ ，将第 $i$ 个石柱直至第 $\min\{i + x - 1, n\}$ 个石柱升高 1 米。最小化使得最后石柱高度单调不降的操作次数。

考虑差分，设 $d_i = h_{i} - h_{i-1}$ 。将单调不降转化为差分序列非负，将区间加转化为差分序列的单点加减。
从前往后遍历差分数组，如果 $d_i < 0$ ，选择 $i$ 进行 $|d_i|$ 次操作即可。
时间复杂度 $O(n)$ 。

G. 二分图判定

题目大意

给定一个序列 $[a_1, a_2, \ldots, a_n]$ ，对满足 $|a_i - a_j| > k$ 的点对 $(i, j)$ 连边。求最小的非负整数 $k$ ，使得生成的图是二分图。

首先，最终的答案与 $[a_1, a_2, \ldots, a_n]$ 的顺序无关，我们不妨假设它是单调不降的。
原问题等价于将 $[a_1, a_2, \ldots, a_n]$ 划分为两个集合 $S$ 与 $T$ ，其中 $S$ 中不存在差大于 $k$ 的元素， $T$ 中也不存在差大于 $k$ 的元素。
也就是说， $S$ 中的元素极差不超过 $k$ ， $T$ 中的元素极差也不超过 $k$ 。换言之，我们需要最小化 $S$ 与 $T$ 极差的最大值。
设 $S$ 中的最大值为 $S_{\text{max}}$ ，最小值为 $S_{\text{min}}$ ，设 $T$ 中的最大值为 $T_{\text{max}}$ ，最小值为 $T_{\text{min}}$
不妨设 $S_{\text{max}} \leq T_{\text{max}}$ 。我们断言，在最优的情况下， $S_{\text{max}} \leq T_{\text{min}}$ 。

证明

Case 1

如果 $S_{\text{min}} \leq T_{\text{min}} \leq S_{\text{max}}$ ，那么将 $T$ 中小于 $S_{\text{max}}$ 的元素放入 $S$ 中不会改变 $S$ 的极差，同时可以让 $T$ 的极差更小。

Case 2

如果 $T_{\text{min}} \leq S_{\text{min}} \leq S_{\text{max}}$ ，那么将 $T$ 中小于 $S_{\text{min}}$ 的元素放入 $S$ 中不会使得 $S$ 的极差超过 $(T_{\text{max}} - T_{\text{min}})$ 。此时问题化为 Case 1。
所以对原序列排序后，我们可以枚举 $S$ 与 $T$ 的分界点，在所有答案中取最小即可。
时间复杂度 $O(n \log n)$ 。

J. 鱼骨挖矿法

题目大意

给定一个二维网格表示矿区。分别求出以第 $i$ 行作为主矿道最终挖掘到矿物的总价值。

对于每一次询问，朴素遍历第 $i$ 行的每一个格子计算在主矿道中进行挖掘时，挖到矿物的价值是容易的。
考虑如何预处理分矿道对答案的贡献。
我们可以将 $\{3k + 1, 3k + 2, 3k + 3\}$ 分为一组。对于一个给定的 $j$ ，它所属的组是确定的。
以挖掘上分矿道的过程为例，记 $up_{i,j}$ 表示从第 $i$ 行第 $j$ 列开始往上挖掘，最终挖掘到的矿物的价值之和。
如果 $v_{i,j} + v_{i-1,j} + v_{i,j-1} + v_{i,j+1}$ 不为 0：
那么 $up_{i,j} = v_{i,j} + v_{i-1,j} + v_{i,j-1} + v_{i,j+1}$
否则 $up_{i,j} = up_{i-1,j}$ 。
类似地，预处理 $down_{i,j}$ 。对于第 $j$ 列的分矿道， $up_{i-2,j} + down_{i+2,j}$ 即为在挖掘主矿道后，挖掘该分矿道时能挖掘到的矿物价值之和。

K. 大师和他的领域

题目大意
给定一个序列 $[a_1, a_2, \ldots, a_n]$ 。一个区间是合法的当且仅当：区间内满足 $a_i > k$ 的元素数量等于满足 $a_i < k$ 的元素数量，且存在满足 $a_i = k$ 的元素。求合法的区间数量。

由于 $k$ 是给定的，所以可以令：

b_i = \begin{cases} 1, & a_i > k, \\ -1, & a_i < k, \\ 0, & a_i = k. \end{cases}

首先记录 $b_i = 0$ 的位置。如果区间 $[l, r]$ 满足 $a_i > k$ 的元素数量等于满足 $a_i < k$ 的元素数量，那么 $\sum_{i=1}^r b_i = 0$ 。
我们可以预处理 $\{b\}$ 的前缀和，然后根据前缀和分组。在每组中枚举下标，然后二分查找最大的边界即可。
时间复杂度 $O(n \log n)$ 。

C. 小 W 的计数题

题目大意
给定一个序列 $[a_1, a_2, \ldots, a_n]$ ，对于满足 $1 \leq x \leq n$ 的每一个 $x$ ，找到元素数量最多的集合 $S_x$ ，其中对于任意的 $y \in S_x$ ， $[a_{\min\{x,y\}}, \ldots, a_{\max\{x,y\}}]$ 的最大值为 $a_y$ 。

对于固定的 $x$ ，考虑如何选择合法的 $y$ 。
不妨设 $y > x$ ，也就是说， $a_y$ 必须是 $[a_x, \ldots, a_y]$ 的最大值。由于 $y$ 是否合法与 $[a_x, \ldots, a_{y-1}]$ 中元素是否放入 $S_x$ 无关，所以每当
$S_y \geq \max_{i=x}^{y-1} \{a_i\}$
时，我们都应将 $a_y$ 加入 $S_x$ 中。 $y < x$ 的情况同理。
要维护满足 $y > x$ 的 $y$ 的数量，我们可以使用单调栈从后往前扫一遍整个序列，弹出比当前元素值小的栈顶元素，当前栈中元素数量即为满足满足 $y > x$ 的 $y$ 的数量。
维护 $y < x$ 的情况同理。注意对于给定的 $x$ ， $y = x$ 一定可以放入 $S_x$ 中。
时间复杂度 $O(n)$ 。

D. 美丽的 01 串

题目大意

给定一个 01 串，选择若干个长度大于 1 的子串删除，使得删除后的 01 串中 ‘0’ 的数量等于 ‘1’ 的数量。最小化删除的子串的长度之和。

不妨设 ‘0’ 的数量小于等于 ‘1’ 的数量。记 ‘0’ 的个数为 $m$ ，记第 $i$ 个 ‘0’ 与第 $i+1$ 个 ‘0’ 之间存在 $a_i$ 个 ‘1’。特别地，记第 1 个 ‘0’ 之前存在 $a_0$ 个 ‘1’，记第 $m$ 个 ‘0’ 之后存在 $a_m$ 个 ‘1’。
记 ‘1’ 的数量比 ‘0’ 的数量多 $d$ ，于是 $\sum_{i=0}^m a_i = m + d$ 。
首先，答案的下界为 $d$ 。

Case 1

$d = 0$ 时，我们不需要删除任何子串，答案为 0。

Case 2

$d$ 为大于 0 的偶数时，我们断言
$\sum_{i=0}^{m} \lfloor \frac{a_i}{2} \rfloor \geq \frac{d}{2}$

证明

假设
$\sum_{i=0}^{m} \lfloor \frac{a_i}{2} \rfloor < \frac{d}{2}$
注意到
$\frac{a_i}{2} - \frac{1}{2} \leq \lfloor \frac{a_i}{2} \rfloor$
其中等号当且仅当 $a_i$ 为奇数时成立。
我们有：
$\frac{d}{2} - 1 \geq \sum_{i=0}^{m} \lfloor \frac{a_i}{2} \rfloor \geq \sum_{i=0}^{m} (\frac{a_i}{2} - \frac{1}{2})$
整理得：
$\sum_{i=0}^{m} a_i \leq m + d$
其中等号当且仅当 $a_i$ 均为奇数时成立。
又因为 $\sum_{i=0}^m a_i = m + d$ ，当 $a_i$ 均为奇数时，左式与 $m + 1$ 模 2 同余；又因为 $d$ 为偶数，矛盾。所以 $a_i$ 不全为奇数，等号即无法成立，从而 $\sum_{i=0}^m a_i < m + d$ 。这与 $\sum_{i=0}^m a_i = m + d$ 矛盾。
所以 $\sum_{i=0}^m \left\lfloor \frac{a_i}{2} \right\rfloor \geq \frac{d}{2}$ 。
所以，存在至少 $\frac{d}{2}$ 个长度为 2 的子串 “11”。我们只需要删除它们即可。答案为 $d$ 。

Case 3

$d = 1$ 时，由于原串的长度大于等于 2，所以 ‘1’ 的个数大于等于 2，‘0’ 的个数大于等于 1。
如果不存在满足 $a_i \geq 2$ 的 $i$ ，又因为 $\sum_{i=0}^m a_i = m + 1$ ，所以对于 $0 \leq i \leq m$ ，都有 $a_i = 1$ ，取 $A_1A_2A_3$ 删除即可。此时删除的子串总长度为 3。另一方面，删除子串的总长度大于等于 2，又因为删除子串的总长度为偶数时，不改变 ‘1’ 的个数与 ‘0’ 的个数之差的奇偶性，所以最小的删除子串总长度即为 3。
如果存在满足 $a_i \geq 2$ 的 $i$ ，由于 ‘0’ 的个数大于等于 1，所以我们可以很容易地找到一段连续的 “110” 或者 “011” 并删除。同理，这是最优的操作方式，删除子串的总长度为 3。

Case 4

当 $d$ 为大于等于 3 的奇数且 $\max_{i=0}^{m}\{a_i\} \leq 2$ 时，如果我们只删除 ‘1’，我们每次只能删除长度为 2 的子串而无法改变差值的奇偶性。
这意味着我们必须删除 ‘0’，从而答案的下界为 $d+2$ 。
由于 $d \geq 3$ ，所以一定存在满足 $a_i \geq 2$ 的 $i$ 。根据在 Case 3 中的讨论，我们可以很容易找到一个长度为 3 的子串，其中包含 2 个 ‘1’ 与 1 个 ‘0’。从而问题化归为 Case 2。需要删除的子串长度之和为
$3 + (d-1) = d+2$ 。

Case 5

当 $d$ 为大于等于 3 的奇数且 $\max_{i=0}^{m}\{a_i\} \geq 3$ 时，我们可以选择一个“111”删除，将问题化归为 Case 2。需要删除的子串长度之和为 $3 + (d - 3) = d$ 。

E. 更美丽的区间

题目大意

给定一个序列 $[a_1, a_2, \ldots, a_n]$ ，与一个满足 $\sqrt{n} \leq x \leq n$ 的 $x$ 。对于每一个 $i$ ，找到最小的 $r_i$ ，使得 $[i, r_i]$ 中的元素出现次数均不低于 $x$ 。

首先，由于 $x \geq \sqrt{n}$ ，所以出现次数大于等于 $x$ 的元素种类不超过 $\sqrt{n}$ 种。
另一方面，出现次数小于 $\sqrt{n}$ 的元素一定不能包含在区间内。所以我们可以将原序列划分成若干个子段进行处理。
考虑模拟朴素实现。假设当前的左端点为 $L$ ，当我们枚举到 $a_i$ 时，我们的区间右端点 $R$ 至少需要满足： $a_i$ 在 $[L, R]$ 内的出现次数不低于 $x$ 次。记下标 $j$ 满足： $a_j = a_i$ 且 $[i, j]$ 中恰有 $x$ 个 $a_i$ ，我们可以拿 $j$ 与当前区间右端点的最大值去更新区间右端点。如果不存在这样的 $j$ ，说明对于左端点为 $L$ 的情况，答案不存在。
实际上，我们可以倒序枚举左端点，记录每种元素出现的位置，同时使用 set 记录当前左端点右边每种元素第一次出现的位置，然后模拟上述过程即可。
对于一个给定的左端点 $L$ ，我们只需要枚举至多 $\frac{n}{x}$ 次即可完成模拟过程。最终的时间复杂度为 $O\left(\frac{n^2}{x} + n\log n\right)$ 。

F. 冠军之路

题目大意

给定一棵无根树和 $m$ 名运动员的位置。多次独立的询问，每次给出小明的起点和比赛的终点，判断比赛的结果。

首先使用多源 BFS 预处理每个点到这 $m$ 名运动员的距离的最小值。记点 $i$ 到这 $m$ 名运动员的距离的最小值为 $f_i$ 。
记 $dis_{u,v}$ 表示点 $u$ 与点 $v$ 的距离。
当给定小明的起点 $x$ 与比赛的终点 $y$ 时，如果 $dis_{x,y} > f_y$ ，那么显然小明无法获得冠军，答案为 $-1$ ；如果 $dis_{x,y} < f_y$ ，那么小明是唯一冠军，答案为 0。
当 $dis_{x,y} = f_y$ 时，存在一个位于从 $x$ 到 $y$ 的路径上的点 $z$ ，使得小明与其他运动员第一次在 $z$ 相遇。
这也就说明，对于小明到达 $z$ 之前经过的所有点 $i$ ，都有 $dis_{x,i} \neq f_i$ ; 否则小明会和某一名运动员在 $i$ 相遇，矛盾。
显然，对于从 $z$ 到 $y$ 的路径上的所有点 $j$ ，都有 $dis_{x,j} = f_j$ 。
于是我们可以二分 $z$ 到 $x$ 的距离 $d$ ，然后倍增求出从 $x$ 到 $y$ 的路径上，与 $x$ 的距离为 $d$ 的点 $m$ ，判断 $dis_{x,m}$ 与 $f_m$ 是否相等即可。
时间复杂度 $O(n + q \log^2 n)$

华中农业大学第十五届程序设计竞赛（新生赛）题解

试题讲解

L. 山海之约

题目大意

I. 学霸题

H. 对决

题目大意

B. 爱的魔法

题目大意

A. 矩阵游戏

题目大意

M. 终极考验

题目大意

G. 二分图判定

题目大意

证明

Case 1

Case 2

J. 鱼骨挖矿法

题目大意

K. 大师和他的领域

C. 小 W 的计数题

D. 美丽的 01 串

题目大意

证明

E. 更美丽的区间

题目大意

F. 冠军之路

题目大意