Zihim

编辑于 03-29 16:14 美国

2026年广东工业大学揭阳校区程序设计竞赛题解

A - 外卖领域大神

思路

本题是一个带有顺序约束的旅行商问题（TSP）的变种，由于任务数较少，因此考虑使用状态压缩动态规划（状压 DP）求解。

由于整个图的结构和权重在 $q$ 天内是固定不变的，我们需要先使用一次 Floyd-Warshall 算法或使用 $n$ 次 Dijkstra 算法在 $O(n^3)$ 或 $O(nm\log n)$ 时间内预处理任意两个地点 $i, j$ 之间的最短通行时间 $D(i,j)$ （若无法到达则设为无穷大）。

对于某一天的 $k$ 个任务，使用一个 $k$ 位的二进制数 $S$ 来表示当前已经完成的任务集合（第 $i$ 位为 $1$ 表示第 $i+1$ 个任务已完成）。定义 $f(S,i)$ 表示已经完成的任务集合 $S$ ，且当前最后完成的任务是 $i$ 时的最短耗时。

设第 $i$ 个任务所在的地点为 $h_i$ ，由题定义从地点 $i$ 到地点 $j$ 的最短耗时 $C(i, j)$ 为

C(i,j)=\left\{\begin{aligned} &0, &i=j \\ &D(i,j)+d_{j}, &i\not=j \\ \end{aligned}\right.

从起点 $s$ 出发后完成的第一个任务必然是取餐任务，因此进行第一步的转移：

f(2^i,i)=d_s+C(s,h_i)

遍历当前状态 $S$ 和当前任务 $i$ ，考虑接下来的任务 $j\ (j\not\in S)$ ：

若任务 $j$ 为取餐任务，直接转移。
若任务 $j$ 为送餐任务，必须保证其依赖的取餐任务 $p_j\in S$ ，否则不能转移。

转移方程为（即更新最小值）：

f(S+2^j,j)=\min\{f(S+2^j,j),f(S,i)+C(h_i,h_j)\}

当所有任务都完成后有 $S=2^k-1$ ，此时需要从当前任务所在地 $h_i$ 前往终点 $t$ ，答案即为

\min_{0\le i<k}\{f(2^k-1,i)+C(h_i,t)\}

预处理最短路时间复杂度为 $O(n^3)$ ，空间复杂度为 $O(n^2)$ 。状压 DP 复杂度为 $O(k^22^k)$ ，空间复杂度为 $O(k 2^k)$ 。总时间复杂度为 $O(n^3+qk^22^k)$ ，总空间复杂度为 $O(n^2 + k 2^k)$ 。

B - 淮水竹亭

思路

题目要统计长度为 $m$ 的安全字符串个数，而“不安全”的判定方式是：是否包含某个禁忌符文作为连续子串。

看到“多模式串 + 子串匹配 + 计数”，基本就该往 AC 自动机上靠了。

如果只给一条禁忌符文，我们会想做一个自动机，记录当前后缀和模式串前缀匹配到了哪里。

现在禁忌符文有很多条，但想法其实没变：我们依然想在构造字符串的过程中，随时知道“当前后缀可能接在哪些禁忌符文前缀后面”。AC 自动机正是干这个的。

建完 AC 自动机后，每个状态都代表“当前字符串的某个最长后缀，对应到了若干禁忌符文前缀”。如果某个状态本身就是某条禁忌符文的结尾，或者沿着失配链能走到某条禁忌符文的结尾，那么一旦到达这个状态，说明当前字符串已经出现了禁忌符文，不再安全。

于是问题就变成在 AC 自动机上从根出发走 $m$ 步，其中每一步可以补一个小写字母，但整条路径不能经过任何“坏状态”。这就是一个长度 DP。

先把所有禁忌符文插入 Trie，并建立 AC 自动机。

设状态 $u$ 是坏状态，当且仅当 $u$ 本身对应某条禁忌符文的结尾；或 $u$ 的失配链上存在这样的结尾状态。

然后定义 $dp[l][u]$ 为构造了长度为 $l$ 的前缀，且当前停在自动机状态 $u$ 的安全方案数。

初始时 $dp[0][root]=1$ ，转移时枚举下一个字符 $c$ ，走到自动机中的下一状态 $v$ 。只有当 $v$ 不是坏状态时，这个转移才合法：

dp[l+1][v] = dp[l+1][v] + dp[l][u]

最后把所有长度为 $m$ 且停在非坏状态的方案数求和即可。由于转移只依赖上一层，DP 可以直接滚动数组优化成两行。

所有禁忌符文长度总和不超过 $1000$ ，设 AC 自动机状态数为 $S$ ，建自动机时间复杂度为 $O(S \cdot 26)$ ，动态规划时间复杂度为 $O(m \cdot S \cdot 26)$ ，空间复杂度为 $O(S)$ 。

C - 太极

思路

这是一个公平组合博弈游戏，它有一个引理：

没有后继状态的状态是必败状态。
若某状态存在一个后继状态为必败状态，则该状态为必胜状态。
若某状态的所有后继状态均为必胜状态，则该状态为必败状态。

对于先手而言，根据第一条， $0\le n< a$ 均为必败状态。另外，对应于游戏中的取巧克力操作，可以发现一个状态 $n\ (n\ge a)$ 的后继状态为 $n-a,n-a+1,\dots,n-b$ 。

将状态往后递推，用数学归纳法不难证明对于所有 $k\in\mathbb N^*$ ，

k(a+b)\le n<k(a+b)+a

均为必败状态，其它均为必胜状态。因此根据输入判断初始状态是否为必败状态，若是则选择后手，否则选择先手。

由于交互器是适应性的，因此需要确保每一轮操作后都将小智置于在必败状态中，否则会被小智反杀。

可以发现必败状态模 $(a+b)$ 同余，因此一个简单的策略就是在小智取走 $x$ 个巧克力后再取走 $a+b-x$ 个巧克力（不难发现 $a\le a+b-x\le b$ ，因此总是可以取到的）。

如果是先手，需要先将小智置于在必败状态中，稍加研究不难发现取

\min\{\max\{a,r-(a-1)\},b\}

个巧克力是可行的，其中 $r=n\bmod(a+b)$ 。

每次决策的时间复杂度和空间复杂度均为 $O(1)$ 。

D - 纯爱天篇

思路

由恒等式

a+b=(a\oplus b)+2(a\mathbin{\&} b)

立刻得到

a\mathbin{\&} b = \frac{n-m}{2}

此时判断无解的情况即为 $n\not\equiv m\pmod 2$ 或 $n<m$ 。

设 $c=\frac{n-m}{2}$ ，接下来按位看就很清楚了：

若某一位在 $m=a\oplus b$ 中是 $1$ ，说明这一位只能出现在 $a,b$ 中的某一个数里；
若某一位在 $c=a\ \&\ b$ 中是 $1$ ，说明这一位必须同时出现在 $a,b$ 里。

故还要保证 $m\ \&\ c=0$ ，否则无解。

若要使 $a\times b$ 尽可能小，他们的差要尽可能大，故应将 $m$ 中为 $1$ 的位给 $a$ ，最优解为

\left\{ \begin{aligned} a &= \frac{n+m}{2} \\ b &= \frac{n-m}{2} \\ \end{aligned} \right.

时间复杂度和空间复杂度均为 $O(1)$ 。

E - 愚公移山

思路

硬度和高度是障眼法，实际上只需要记录第 $i$ 座山需要进行 $c_i=a_i\cdot b_i$ 次神铲操作。

假如不允许不使用圣符，贪心可以发现需要发动神铲的最少次数为

c_1+\sum_{i=2}^n\max(0,c_i-c_{i-1})

因此枚举圣符的位置，圣符会将整座山分为独立的两部分，每个部分其实就是上述问题的子问题。

可以 $O(n)$ 预处理前缀和 $p(i)=p(i-1)+\max(0,c_i-c_{i-1})$ 及后缀和 $q(i)=q(i+1)+\max(0,c_i-c_{i+1})$ 的答案，然后在 $O(n)$ 时间内枚举圣符并取 $p(i-1)+q(i+1)$ 的最小值。

F - 棋魂——纹枰新秀

思路

连通块搜索模拟题。

先数出黑子和白子的个数，再利用广度优先搜索把所有空位 . 按上下左右连通性分块。对每一块空位，看看它只挨着黑子、只挨着白子，还是两边都挨着。

如果一整块空位只与黑子相邻，那么这整块都是黑方地盘；只与白子相邻就归白方；若同时挨着黑白，或者干脆谁都不挨着，那这一块就不计分。

由于棋盘固定大小，且深度优先搜索不重复，总时间复杂度 $O(1)$ 。

G - 涂山续缘

思路

根据二进制下按位与的性质，很显然

\left\{\begin{aligned} a\ \&\ b &\le a \\ a\ \&\ b &\le b \\ \end{aligned}\right.

故每次合并并不会使结果更差，所以直接把整个序列全部合并成一个数，最后得到的必然是答案。

遍历数组的时间复杂度为 $O(n)$ ，数组空间复杂度 $O(n)$ ，一边输入一边按位与可以做到 $O(1)$ 空间复杂度。

H - 数学题

思路 1

此题并不算是一道好题，矩阵快速幂模板题。

定义 $\mathbf{v}_n=\begin{bmatrix} a_n \\ a_{n-1} \\ 5^n \\ n \\ 1 \\ \end{bmatrix}$ ， $\mathbf{M}=\begin{bmatrix} 1 & 2 & 4 & 3 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}$

由题可推得基于矩阵的递推式及通项式

\begin{aligned} \mathbf{v}_n&=\mathbf M{\mathbf v}_{n-1} \\ &={\mathbf M}^{n-1}{\mathbf v}_1 \end{aligned}

利用矩阵快速幂求得 $\mathbf{v}_n$ 即可得到 $a_n$ 。

此处矩阵乘法是常数级别的。故时间复杂度为 $O(q\log n)$ 。

思路 2

利用待定系数法将递推式变形为

b_n=b_{n-1}+2b_{n-2}

其中

b_n=a_n-\frac29\times5^{n+2}+\frac32n+\frac{15}4

这是一个二阶齐次线性递推方程，其中

b_0=-\frac{29}{36} \\ b_1=-\frac{775}{36}

利用特征根法可以解得

b_n=\frac{239}{36}{(-1)}^n-\frac{67}{9}2^n

因此解得

36a_n=239{(-1)}^n-268\cdot2^n+200\cdot5^n-54n-135

根据此式，利用普通的快速幂及 $36$ 在模 ${10}^9+7$ 下的逆元即可计算结果。时间复杂度亦为 $O(q\log n)$ 。

I - 上课

思路

先考虑对于特定某次的课程安排，利用逆向思维贪心。首先假设 $m=1$ ，要覆盖所有的课程，小智必须从第一节课（设时间点为 $l$ ）一直待到最后一节课（设时间点为 $r$ ）。此时在教学楼的总时间为 $r-l+1$ 。

但是题目允许我们选择至多 $m$ 个时间段，这意味着我们可以从完整的 $[l,r]$ 区间中，选择至多 $m-1$ 个“连续无课时间段”（即两个相邻 1 之间的 0 串），在这期间回宿舍休息。为了让总时间最短，我们应该尽可能贪心地选择最长的无课间隙，若选择的总长为 $t$ ，所求答案即为

r-l+1-t

接下来考虑修改的情况。由于每次只修改一个点，我们可以利用多重集（如 C++ 中的 std::multiset，底层是红黑树）动态维护所有上课的时间点集合以及无课间隙集合。

首先利用二分查找找到 $x$ 在集合中位置，并找出其前驱 $p$ 和后继 $q$ 。

添加课程时：
- 如果 $p,q$ 均存在，说明 $x$ 将原本的一个大无课间隙切分成了两半。我们需要从间隙集合中删除原间隙 $q-p-1$ ，并加入两个新间隙 $x-p-1$ 和 $q-x-1$ 。
- 否则，说明 $x$ 成为了新的边界（新的第一节课或最后一节课），原边界和 $x$ 之间会产生一个新的无课间隙，直接将其加入集合即可。
删除课程时：
- 如果 $p,q$ 均存在，说明 $x$ 被移除后，原本被它隔开的两个小间隙会连成一个大间隙。我们需要从间隙集合中删除两个旧间隙 $x-p-1$ 和 $q-x-1$ ，并加入合并后的新间隙 $q-p-1$ 。
- 否则，说明移除了一个边界。直接把原本与该边界相邻的无课间隙从集合中删除即可。
最后将 $x$ 从上课位置集合中移除。

为了快速求出前 $m-1$ 大的无课间隙之和，这里需要一个能够支持动态插入、删除，并随时查询前 $m-1$ 大元素和的数据结构。例如再使用两个多重集来协作完成：

Top-k 集合 $A$ 存储当前最大的 $m-1$ 个无课间隙，用 $t$ 维护其中元素的和。
集合 $B$ 存储其余较小的无课间隙。

插入元素时，如果 $A$ 还没满，或者新元素大于 $A$ 中的最小值，则将新元素放入 $A$ ，并将 $t$ 加上其值，否则放入 $B$ 。

删除元素时，如果被删除元素在 $A$ 中，则从中删除并将 $t$ 减去对应的值；如果不在，则从 $B$ 中删除。

注意在每次插入或删除后，如果 $|A|<m-1$ 且 $|B|>0$ ，就把 $B$ 中的最大值移入 $A$ ；如果大于 $|A|>m-1$ ，就把 $A$ 中的最小值移到 $B$ 中。每次移动同步更新 $t$ 。

当然，使用多个树状数组维护也是可以的，总之要维护的只有三个内容：

当前所有上课时间点的位置；
所有相邻上课时间点之间的无课间隙长度；
最大的若干个无课间隙之和。

初始化时间复杂度 $O(n \log n)$ ，翻转总时间复杂度 $O(q\log n)$ 。空间复杂度为 $O(n)$ 。

J - 裂变

思路

如果可以，我们优先构造 $\gcd(a,b)=1$ 的 $a,b$ 。

利用一些经典互质结论（如相邻两个数互质，相邻两个奇数互质，差为 $4$ 的两个奇数互质）分类讨论构造符合要求的解：

若 $n=4k$ ，输出 $2k-1$ 和 $2k+1$ 。特判 $n=4$ 时输出 $2$ 和 $2$ 。
若 $n=4k+1$ ，输出 $2k$ 和 $2k+1$ 。
若 $n=4k+2$ ，输出 $2k-1$ 和 $2k+3$ 。特判 $n=6$ 时输出 $2$ 和 $4$ 。
若 $n=4k+3$ ，输出 $2k+1$ 和 $2k+2$ 。

时间复杂度和空间复杂度均为 $O(1)$ 。

K - Nari国的反击

思路

化简两个关键约束的公式得到

\begin{aligned} f(x,y) &= 2px + 2qy \\ g(x,y) &= tx + sy + st \\ \end{aligned}

考虑将其写成矩阵乘法与向量加法的仿射变换形式

\begin{bmatrix} 2p & 2q \\ t & s \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix} + \begin{bmatrix} 0 \\ st \\ \end{bmatrix} = \begin{bmatrix} f(x,y) \\ g(x,y) \\ \end{bmatrix}

这相当于对军事基地的核心区域中的原始坐标 $(x,y)$ 执行了一次仿射变换，映射为新坐标 $(f(x,y),g(x,y))$ 。

原问题就变成：核心区域里的点，经过这个变换后，哪些会落在整数格点上。

凸包退化成一个点时，这个点坐标本身就是整数，因此两条线性表达式的值也一定是整数，答案为 $1$ 。
凸包退化成一条线段时，
- 若仿射矩阵为零矩阵，说明在线段上移动时，两条表达式都不变，而线段端点又对应整数值，所以整条线段上的点都是有效打击目标，答案无穷。
- 否则，对线段端点应用上述仿射变换，不难发现端点为 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的线段上的格点数为：
  $\gcd{(|x_1-x_2|,|y_1-y_2|)}+1$
凸包是二维多边形时，先看矩阵行列式

$\det(M)=2ps-2qt$
- 若 $\det(M)=0$ ，说明两条整性约束线性相关，变换后的整个凸包会压成一条整点线段。原平面中对应的是若干条平行线与多边形相交，其中至少有一条会切出非零长度线段，所以有效打击目标无穷多，输出 Koji orz。
- 若 $\det(M)\ne 0$ ，该变换是一个双射，此时原核心区域内满足条件的有效打击目标数量，严格等于变换后的新多边形区域内（含边界）的格点数量。
  
  根据相关几何定理，仿射变换会保持图形的凸性。使用 Andrew 算法或 Graham 扫描法对所有输入点求凸包，得到军事基地的核心区域的各个顶点。然后对这些顶点应用上述仿射变换，得到变换后的新凸包顶点（也可以先对所有点变换再求凸包）。
  
  根据皮克定理：
  $S=I+\frac B2-1$
  其中 $S$ 为多边形面积， $I$ 为多边形内部格点数， $B$ 为多边形边界上的格点数。答案即为总格点数 $I + B$ ，移项：
  $I+B=S+\dfrac B2+1$
  对于多边形边界上的格点数 $B$ ，遍历多边形所有的边进行格点计算并求和即可得到整体的 $B$ 。
  
  对于多边形面积 $S$ ，根据多边形顶点坐标使用鞋带公式计算：
  $S = \frac{1}{2} \left| \begin{vmatrix} x_1 & x_2 \\ y_1 & y_2 \end{vmatrix} + \begin{vmatrix} x_2 & x_3 \\ y_2 & y_3 \end{vmatrix} + \cdots \begin{vmatrix} x_{n-1} & x_n \\ y_{n-1} & y_n \end{vmatrix} + \begin{vmatrix} x_n & x_1 \\ y_n & y_1 \end{vmatrix} \right|$
  计算出 $S$ 与 $B$ 后，代入 $S+\dfrac B2+1$ 即可求得最终的有效打击目标个数。

求凸包的时间复杂度为 $O(n \log n)$ 。后续分类讨论和计算的时间复杂度为 $O(n)$ 。另外，空间复杂度为 $O(n)$ 。

L - 小陈喜欢逛基地

思路

题目要求经过每个方格恰好一次，并最终回到起点，同时让末影珍珠数量最少。

不难发现由于周期性（完成时会经过每个点各一次且回到原处），可以抛弃 $(a,b)$ ，假设初始就在 $(1,1)$ 。

把“移动到相邻格子”看成网格图上的边，这件事本质上就是：

不用末影珍珠时，要求找一个 Hamilton 回路；
用一次末影珍珠时，等价于找一条 Hamilton 路径，然后在某一处把不相邻的两端接起来。

矩形网格的 Hamilton 回路存在性是经典结论，自行推导也是容易构造的：

若 $n=1$ 或 $m=1$ ，只有 $1 \times 2$ 和 $2 \times 1$ 这两种长度为 $2$ 的情况能成回路，否则有 Hamilton 路径。
若 $n,m>1$ ，当且仅当 $n,m$ 中至少有一个是偶数时，存在 Hamilton 回路，否则有 Hamilton 路径。

若 $n=1$ 或 $m=1$ ，构造非常简单，不予赘述，当 $n,m>1$ 时， $n,m$ 中至少有一个是偶数时构造形如下：

此时不需要末影珍珠。否则构造形如下：

构造与输出整条路线需要 $O(nm)$ 时间，空间复杂度为 $O(nm)$ ，利用上述构造的特性可以简化到 $O(1)$ 。

M - 让我成为你的眼睛

思路

首先意识到是需要找满足特定要求的最长上升子序列。

除此之外，不需要考虑计算灵压之和，实际上根据几何级数的性质可以发现灵压之和与子序列下标的字典序一一对应。

因此需要寻找下标字典序最小和下标字典序最大的子序列。

我们知道，在求解最长上升子序列时，可以维护一个数组 $f$ ，其中 $f(k)$ 表示长度为 $k$ 的上升子序列的末尾元素的最小值。通过二分查找，我们能在 $O(n\log n)$ 的复杂度内求出 LIS 的最大长度 $L$ 。

先寻找下标字典序最大的子序列，我们需要在正向遍历原数组 $a$ 时，额外记录一个数组 $b$ ，其中 $b_i$ 表示以第 $i$ 个元素 $a_i$ 结尾的最长上升子序列的长度（即 $a_i$ 在 $f$ 数组中通过二分查找更新的那个长度）。

求出所有的 $b_i$ 以及最大长度 $L$ 后，可以通过倒序遍历来贪心重构：

设当前我们需要寻找的最长上升子序列长度目标为 $l$ （初始值为 $L$ ），并记录上一个被选入剑阵的法力值为 $t$ （初始可视为正无穷）。
倒序遍历数组 $b$ 。如果遇到一个下标 $i$ 同时满足 $b_i = l$ 且 $a_i < t$ ，我们就立刻选中第 $i$ 把剑，并更新 $t = a_i$ ，同时将目标长度 $l$ 自减。
重复此过程，直到 $l = 0$ 为止。