NEUACM 2025 Winter Training 4 题解

D 运输计划

题意

一个 $n$ 个点的树，每条边的边权，给出 $m$ 条路径。要求只改变一条边的边权，使得所有路径中长度最大的路径的长度最小。

$n, m \le 3 \times 10^5$。

分析

“最大值最小”提示我们要二分答案。假设我们当前要求最大路径长度不能超过 $d$。那么所有长度大于 $d$ 的路径中都要包含操作的边，且操作的边的边权应当大于等于该路径的原长与 $d$ 的差。
更进一步，这条边的边权应当大于等于所有路径长度最大值与 $d$ 的差。所以，我们可以树上差分来给超过 $d$ 的路径打标记，然后去遍历每一条边，查看是否存在一条边被所有的标记覆盖且边权大于等于路径长度最大值与 $d$ 的差。

E 通配符匹配

题意

几乎所有操作系统的命令行界面（CLI）中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个是星号（*），可以匹配 0 个及以上的任意字符：另一个是问号（?），可以匹配恰好一个任意字符。现在需要你编写一个程序，对于给定的文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。

对于 $100 \%$ 的数据

• 字符串长度不超过 $100000$
• $1 \le n \le 100$
• 通配符个数不超过 $10$

分析

注意到通配符个数不超过 $10$，所以我们尝试从这里入手。首先我们可以把模式串用通配符分割成 $h$ 段，其中每一段为确定的字符串或第一个字符为通配符剩下的字符为字符串。例如 a*b?c 会被分割为 a、*b 和 ?c 三部分。

定义状态 $f_{k, i}$ 表示待匹配串在第 $i$ 个字符处能否匹配到第 $k$ 段结尾。

接着考虑如何转移。我们用 $\mathrm{str}$ 表示模式串， $s$ 表示待匹配串，$\mathrm{pos}_k$ 表示第 $k$ 段结尾位置，$\mathrm{len}_k$ 表示第 $k$ 段长度。

若第 $k$ 段为确定的字符串，那么直接匹配再从前一段转移即可，即 $f_{k, i} = [f_{k - 1, i - \mathrm{len}_k} \wedge \mathrm{str}_{\mathrm{pos}_k - \mathrm{len}_k + 1, \mathrm{pos}_k} = s_{i - \mathrm{len}_k + 1, i}]$。

若第 $k$ 段为开头为 ? 的字符串，那么直接匹配确定的部分，再跳过前一个字符转移即可，即 $f_{k, i} = [f_{k - 1, i - \mathrm{len}_k} \wedge \mathrm{str}_{\mathrm{pos}_k - \mathrm{len}_k + 2, \mathrm{pos}_k} = s_{i - \mathrm{len}_k + 2, i}]$。

若第 $k$ 段为开头为 * 的字符串，那么直接匹配确定的部分，再跳过若干字符转移即可，即 $f_{k, i} = [\exists(j \le i - \mathrm{len}_k + 1 \wedge f_{k - 1, j}) \wedge \mathrm{str}_{\mathrm{pos}_k - \mathrm{len}_k + 2, \mathrm{pos}_k} = s_{i - \mathrm{len}_k + 2, i}]$。

匹配用字符串哈希即可。

I Mex Game

题意

给定一个长度为 $n+1(1 \le n \le 2 \times 10^5)$ 的字符串 $s$。共 $n$ 轮游戏，第 $i$ 轮进行 $i$ 次操作，每轮均由 Alice 先，与 Bob 交替往集合 $X$ 中加入非负整数（一次加入即一次操作）。对于每一轮，记 $x=\mathrm{mex}(X)$，若 $s_x$ 为 $\texttt{A}$ 则 Alice 胜，反之 Bob 胜。对于每一轮，输出谁胜。

分析

集合 $A$ 中的数不可能成为 $x$，所以两人的策略都是不断加入下一个另一个人的字母出现的位置。又因为操作 $i$ 次后，$x$ 可能出现的范围为 $[0, i]$。所以我们只需要统计 $[0, i]$ 中 $\texttt{A}$ 和 $\texttt{B}$ 出现的次数。如果对方字母出现的次数比自己能操作的次数多则输。

K Tree Edges XOR

题意

$n$ 个点，$m$个询问。

给你一棵树的括号序列，输出它的直径。

有 $m$ 次询问，每次询问表示交换两个括号，输出交换两个括号后的直径（保证每次操作后都为一棵树）

输出共 $m+1$ 行。

$3 \le n \le 100000, 1 \le q \le 100000$

分析

括号序列相当于表示了一次 $\text{DFS}$ 遍历树，($ 表示进入子树，) 表示回到父亲。那么一条路径的长度就是一段形如 )))))((( 的字符串的长度。

考虑用线段树维护这个序列。假设答案由两个区间合并而来，左边由 $a$ 个 (，$b$ 个 ) 组成，右边由 $c$ 个 (，$d$ 个 ) 组成。那么合并后的答案就是 $a + |b - c| + d$。这里用了一个重要的技巧，用 $\max$ 来去绝对值。$a + |b - c| + d = \max(a + b - c + d, a - b + c + d)$。我们令 $x = a + b$，$y = a - b$，$p = d + c$，$q = d - c$。那么答案就是 $\max(x + q, y + p)$。也就是说，

• $x$ 表示一段区间后缀括号合并后 ) 与 ( 和的最大值
• $y$ 表示一段区间后缀括号合并后 ) 与 ( 差的最大值，
• $p$ 表示一段区间前缀括号合并后 ( 与 ) 和的最大值
• $y$ 表示一段区间前缀括号合并后 ( 与 ) 差的最大值

再考虑如何维护 $x, y, p, q$。

这里以 $x$ 为例。对于线段树上一个节点，$x_p$ 可以直接从右儿子拿来，即 $x_p = x_{rs}$，也可以跨越区间 $x_p = a_l + |b_l + l_r| + r_r$，其中 $l, r$ 表示一个区间合并后 ) 和 ( 的数量。我们用相同的手法去掉绝对值 $a_l + |b_l + l_r| + r_r = \max(a + b - l_r + r_r, a - b + l_r + r_r) = \max(x_l - l_r + r_r, y_l + l_r + r_r)$。这样我们就维护出了 $x$。剩下的同理，我们就用 $x, y, p, q, l, r$ 不断向上合并求出树的直径。