2025年广州大学程序设计竞赛新生赛题解

A. 魔法门禁试炼

知识点：模拟，条件判断

输入四个数 $a,b,c,d$ ，模拟检查是否满足条件 $a < d \ \&\& \ b = c$

B. 漫步大地的游医

知识点：分组背包

不难看出对每一种药材选 $2^x-1$ 个数量就会产生 $x \times v_i$ 的贡献，而选取数量在 $[2^x,2^{(x+1)}-1)$ 之间和选取数量 $2^x-1$ 没有区别。

考虑将相同种类的药材进行划分，设该药材编号为 $i$ ，则对同种类药材划分为 $2^0-1\ 2^1-1\ \dots\ 2^x-1\leq s_i$ 的数量。

考虑背包，设 $dp[w]$ 为选取了 $w$ 个药材的最大总功效，则对任意 $w+2^x-1 \leq k$ ， $dp[w+2^x-1]=max(dp[w+2^x-1],dp[w]+x \times v_i)$ 。

最后答案则是 $w$ 从 $0-k$ 的 $max$ ，为什么不是 $dp[k]$ 的原因是可以选取不产生贡献的药材使得最后选取 $k$ 个药材。

细节部分需要注意的是相同种类的药材只能选取一种取法。

C. 归零者

对于一段长度为 $\text{len}$ 的连续全 $1$ 子串，将其全部变为 $0$ 的最少操作次数为 $\left\lceil \frac{\text{len}}{2} \right\rceil。$ 因此，只需对原字符串进行一次线性遍历，统计每一段连续 $1$ 的长度，并在每段结束时将对应的代价累加，最终即可得到所需的最少操作次数。

D. 小学一年级地理

知识点：前缀和

按照题目的说法，我们可以知道以下的信息：

当如果一个区间属于严格递增的坡地，那么该区间内就不存在转折点，并且左边的节点一定小于右边的节点；
当如果一个区间属于严格递减的坡地，那么该区间内就不存在转折点，并且左边的节点一定大于右边的节点；
当如果一个区间属于山地，那么该区间会有且仅有1个先上升后下降的转折点，即存在一个峰值位置 $k$ ( $l < k < r$ )，使得对于所有的 $i \in [l, k-1]$ ，有 $a_i < a_{i+1}$ ，且对于所有的 $j \in [k, r-1]$ ，有 $a_j > a_{j+1}$ ；
当如果一个区间属于谷地，那么该区间会有且仅有1个先下降后上升的转折点，即存在一个谷底位置 $k$ ( $l < k < r$ )，使得对于所有的 $i \in [l, k-1]$ ，有 $a_i > a_{i+1}$ ，且对于所有的 $j \in [k, r-1]$ ，有 $a_j < a_{j+1}$ ；
当如果一个区间属于其他地形，那么该区间会有2个及以上的转折点。

根据以上的特性，我们就可以利用它判断这个区间的类型，看这个区间有多少个先上升后下降的转折点和多少个先下降后上升的转折点。如果是坡地的话再判断一下两个端点的大小关系即可。

由于是多次询问，我们可以在询问前先对整个地图进行操作，把所有的先上升后下降的转折点和先下降后上升的转折点找出来并标记，然后再记录前缀和，这样在每一次询问时我们都可以快速得知某个区间内转折点的数量。

E. 小学二年级地理

知识点：双指针，队列

按照题目的说法，我们可以知道最后合法的区间一定是一个锯齿的形状，也就是对于区间内的位置 $i$ ( $l \leq i \leq r-2$ )，满足 $a_i < a_{i+1} > a_{i+2}$ 或 $a_i > a_{i+1} < a_{i+2}$ 。那么我们可以假设一开始是先上升还是一开始先下降，总共两种情况。

然后对于每一种情况，我们可以确定某两个相邻的地块的大小关系。然后我们可以注意到，对于连续不符合预期的区间，假设区间长度为 $len$ ，我们可以间隔着修改某些数字，使得修改至少 $\lfloor \frac{len}{2} \rfloor$ 个数字把该区间变成符合预期的区间，那么我们依据这个原理就可以去求得某个区间要多少次修改。

对于某个合法区间 $[l,r]$ ，我们总希望使这个区间长度最大化，所以我们可以右移 $r$ 使得区间内修改次数刚好达到上限。然后当区间长度最大化时，也就是当 $r$ 无法移动时，我们可以右移 $l$ 使得修改次数恰好减1，这样 $r$ 就可以继续向右移动，找到新一个合法区间。我们就可以利用双指针的移动，找到所有合法的区间。

而区间内修改次数的维护，我们可以用一个队列来记录当前区间内连续不符合预期的区间的长度。当 $r$ 进行右移时，若连续不符合预期的区间与前一个重叠，那么就是队尾所记录的长度加1，否则在队末尾新加入一个长度值；当 $l$ 进行右移时，若连续不符合预期的区间与后一个重叠，那么就是队尾所记录的长度减1，否则删除队前面第一个长度值。

最后我们再对所有区间的长度求最大值，就能得到我们想要的答案了。

F. 时光终逝，盛宴永存

知识点：树形DP，数学

记 $f_i$ 表示表演完第 $i$ 节目之后，接下来的演出期望时长；记 $g_i = f_i + a_i$ 表示到达第 $i$ 节目时，接下来的演出期望时长。对于任一节点 $u$ ，有

f_u = \frac{1}{3} \left( 2 a_{v_L} + 2 f_{v_L} + 2 a_{v_R} + 2 f_{v_R} + 2 a_u + f_u \right)

解得

f_u = a_u + a_{v_L} + f_{v_L} + a_{v_R} + f_{v_R}

则

g_u = 2 a_u + g_{v_L} + g_{v_R}

根据此递推关系，一棵树上的期望演出总时长为 $2 \times \sum a$ ，舍去热场节目 $s$ ，答案即为

2 \times \sum a - a_s

题目还要求将G视为一棵二叉树，意味着在该连通分量中 s 的度数最大为 2。对于一已经选择的连通分量 G，如果存在节点 s' 的度数为 3，通过舍弃 s' 的一条边所连接的整个连通分量，令s'成为满足条件的根节点时，答案一定会劣于直接选择被舍弃的连通分量上的一个叶子节点作为根节点。因此，答案的连通分量应当选择森林中一棵完整的树，并挑选一个度数不为 3 的最小节点作为根节点。

遍历整个图即可，复杂度 O(n)。

G. 字符串gcd

知识点：字符串，遍历

根据集合中元素的独立性，我们直接对 $A$ 集合的元素进行遍历，判断其是否存在于 $B$ 集合中，若存在，则插入集合 $\gcd(A,B)$

最后按任意顺序输出即可

H. 学士的书签

知识点：构造

证明 $n \equiv 0 \pmod{3}$ 无解：

因为 $S_n = \frac{n(1+n)}{2},n=3k,k \in N^+$ ，则 $S_n = \frac{3k(1+3k)}{2}$

由于 $S_n \in N^+$ ，则 $\frac{S_n}{3} = \frac{3k(1+3k)}{2 \times 3} = \frac{k(1+3k)}{2}$

考虑 $k$ 是奇数，则 $1+3k$ 为偶数，则 $\frac{S_n}{3} \in N^+$

考虑 $k$ 是偶数，则 $\frac{S_n}{3} \in N^+$

由上述证明可知 $S_n \equiv 0 \pmod{3}$

证明 $n \equiv 2 \pmod{3}$ 无解：

因为 $n+1 \equiv 0 \pmod{3}$ ，则 $S_{n+1} \equiv 0 \pmod {3}$ ， $S_n=S_{n+1}-(n+1) \equiv 0 \pmod{3}$

考虑 $n \equiv 1 \pmod{3}$ 的构造方案：

将所有数看成它们模 $3$ 后的数，即 $0,1,2$

不难看出在没有 $0$ 的时候，第一位无论是填 $1$ 还是 $2$ ，下一位都是固定的。

而如果第一位填了 $2$ ，则发现永远存在 $2$ 个 $1$ 是无法填进去的（ $n=2$ 除外，会剩下 $1$ 个 $1$ ）

这里给出一种构造方案：

$1\ 1\ 2\ 0\ 1\ 2\ 0\ \dots\ 1\ 2\ 0$

以 $n=7$ 为例，则可以构造：

$7\ 1\ 2\ 3\ 4\ 5\ 6$

I. 卡牌游戏 2

知识点：贪心

如果先手出一张后手拥有的手牌时，后手得分并且先后手状态不变，则相当于回合状态 $i=i+1$

如果先手出一张后手没有拥有的手牌时，先后手状态改变，相当于回合状态 $i+1$ 是 $i$ 的反状态

由于先手总是被迫给对手送分（如果打出配对权值），而后手有机会得分，因此成为后手更有利。独有权值的作用正是帮助玩家从不利的先手转为有利的后手。

双方的最优策略可以概括为：

只要手中有独有权值，就先使用独有权值来交换先后手，迫使对手成为先手。

当一方用尽独有权值后，他将一直处于先手，并且只能打出配对权值，从而让对手连续得分，直到游戏结束。

因此，游戏的胜负取决于双方独有权值的数量。设：

$P$ ：配对权值的数量（即双方共同拥有的权值种类数）。

$X = n - P$ ：Momo 独有权值的数量。

$Y = m - P$ ：Jojo 独有权值的数量。

在最优策略下：

若 $X > Y$ ，则 Momo 能够迫使 Jojo 先手打出所有配对权值，从而 Momo 获得全部配对权值的分数，Jojo 得 0 分。

若 $X \le Y$ ，由于 Momo 是先手，Jojo 能够获得全部配对权值的分数，Momo 得 0 分。

需要注意的是 $2$ 张相同权值的卡牌可能会在同一个人的手里

J. 星流萤

知识点：01-BFS

将问题转化为图论最短路径问题。定义状态为三元组 $(x, y, dir)$ ，表示当前位于格子 $(x,y)$ ，且面朝方向为 $dir$ 。其中 $dir \in {0,1,2,3}$ 分别代表上、右、下、左四个方向。

状态之间的转移规则如下：

直行：沿当前方向 $dir$ 移动一步到相邻格子，代价为 $0$ 。

左转：将方向变为 $(dir+3)\bmod 4$ ，然后向新方向移动一步，代价为 $1$ 。

右转：将方向变为 $(dir+1)\bmod 4$ ，然后向新方向移动一步，代价为 $1$ 。

注意不能掉头（旋转 $180^\circ$ ）。

由于第一步可以任意选择方向且不计代价，因此初始状态并非 $(1,1,dir)$ ，而是从 $(1,1)$ 向四个方向走一步所到达的格子及其方向。具体地，对于每个方向 $d$ ，若 $(1,1)$ 向该方向移动一步后到达合法空地 $(x,y)$ ，则初始化状态 $(x,y,d)$ 的距离为 $0$ ，并作为搜索起点。

终止状态为 $(n,m,dir)$ ，其中 $dir$ 任意。最终答案取所有方向下的最小距离。

由于代价只为 $0$ 和 $1$ ，考虑 $01bfs$ 。创建双端队列，如果下一步权值为 $1$ 且需要入队则放入队尾，如果下一步权值为 $0$ 且需要入队则放入队头，每次拿队头的状态进行下一步状态转移。

K. 位运算2

知识点：位运算

容易发现对于 $a,b$ 的每一二进制位而言，相同的对变化都是相同的。除去 $a,b$ 二进制位都是 $0$ 的情况，只剩下 $3$ 种情况： $(1,0),(1,1),(0,1)$ 。

这 $3$ 种情况每种情况两个状态，最后总共 $8$ 种情况，分别讨论或者搜索即可。

L. 最大平均数

知识点：枚举，贪心

可以发现，最大平均数子数组的长度只会为 $2$ 或 $3$ ，长度大于 $3$ 的子数组总能分成左右两个子数组，取平均数最大的那个即可。

枚举左端点，枚举右端点的同时取最大的长度为 $2$ 或 $3$ 的子数组，求和即可。

时间复杂度 $O(n^2)$

M. Nan86

核心的指令其实只有以下两个，可以等效为现实中高级语言的数组赋值

MOV [R1 + R2], R3	# 表示将 `R3` 存储到地址 `R1 + R2` 对应的数组位置中。
					# (int*)R1 = &arr[0], R1[R2] = R3
MOV R1, [R2 + R3]	# 表示将地址 `R2 + R3` 指向的数组元素值加载到 `R1` 中。
					# (int*)R2 = &arr[0], R1 = R2[R3]

由于只能进行加减法运算，可以通过一个表 ATH[X] 来表示运算。通过给定的表格，可以直接使用 ATH[VAL] 进行访问。对于加法和减法，可以通过偏移值来动态查询。

例如，对于简单的 A = A + V，可以构建以下表：

int arr = [-128, -127, ..., -1, 0, 1, ..., 127 ];  addr = &arr[arr.find(0)]

即可转化为

// 假设 A 在 R1 上
MOV R0, addr + V  # R0 = &arr[arr.find(V)]
MOV R0, [R0 + R1] # R0 = *(&arr[arr.find(V)] + R1) = arr[arr.find(V) + R1]

而对于复杂一些的 A = A + B 则需要构建一个二级表

int arr_idx = [&arr[arr.find(-128)], &arr[arr.find(-127)], ... ]

注：此表实际上只用于 if (a<b) 的构建，由于题目只保证了 $-128 < a,b < 128$ ，故实现时应该开一个双倍值域的表

对于 IF 语句，可以考虑构建真假值表，先将当前状态保存到内存 SAVE_TRUE 和 SAVE_FALSE，而后根据 IF 切换。对于 if (a == b) 可以进行 EQ_TAB[a] = True，EQ_TAB[b] = False 对于 if (a < b) 可以构造 LT_TAB = [True ...*n, False ...*n]，通过 a - b 实现条件写入