写在前面

这里是出题人 & 组卷人 $\texttt{Liang_SYEA}$ 。

首先是关于题目难度方面，这一场强度是非常逆天的，整题难度非常高，并且没有太多水题。~~个人区域赛说是。~~

最开始的题有一大堆数论/数据结构/结论，非常恐怖。~~CN刻板印象这一块，另外不要真的变成 THUPC 了啊喂！~~

后来用很多其他部分知识点的题替换掉之后，知识均衡度才能算是合格，也算是稍微减轻了一点点难度~~（微乎其微）~~，但强度依旧逆天。

🥺🥺大家骂轻点🥺🥺

$\text{fun fact}$ ：来自 $GPT$ 大人的评价：

alt

然后数据部分： $A$ 相邻消除这道题，由于出题人忘了放极限数据，导致一开始放过了一车 $O(n^2)$ 的做法，好在才开赛没多久，大约在开赛半小时时修复了数据。

🥺请大家狠狠拷打 $\texttt{BlackCat}$ 喵🥺

另外一个 $\text{fun fact}$ ：由于开线下赛的时候漏了一个题，导致此题变成同步赛专享防 $AK$ 了。

alt

唉唉，不过好在比赛还是顺利办完了。

预测难度

按照同步赛题目编号：

$\texttt{easy}$ ： $D$ 、 $J$
$\texttt{easy-mid}$ ： $K$ 、 $H$ 、 $E$
$\texttt{mid}$ ： $M$ 、 $F$ 、 $C$
$\texttt{mid-hard}$ ： $L$ 、 $B$ 、 $A$
$\texttt{hard}$ ： $I$ 、 $G$

实际难度

按照同步赛题目编号：

$\texttt{easy}$ ： $D$ 、 $J$
$\texttt{easy-mid}$ ： $H$ 、 $K$ 、 $E$
$\texttt{mid}$ ： $B$
$\texttt{mid-hard}$ ： $C$ 、 $L$ 、 $A$
$\texttt{hard}$ ： $I$ 、 $F$ 、 $G$ 、 $M$

solution

A 相邻消除

我们定义 $S_{i, j}$ 表示数组 $a[i\dots j]$ 经过彻底化简后的结果。

根据拼接逻辑，显然有：

S_{1, j} = S_{1, i} \oplus S_{i + 1, j}

其中 $\oplus$ 表示字符串拼接化简的操作。

对于 $\oplus$ 操作，一个字符串的逆元等于它的反转，并且“消除相邻相同字符”的操作具有结合律。

故有：

S_{i + 1, j} = S_{1, i}^{-1} \oplus S_{1, j}

因此我们所求的 $|S_{i + 1, j}|$ ，等于 $|S_{1, i}^{-1} \oplus S_{1, j}|$ 。

我们用一颗 $trie$ 树来表示数组的前缀状态。

维护一个栈来模拟消除的过程：

当元素入栈时，在树上向子节点走一步。
当元素出栈时，在树上向父节点回退一步。

这样每一个前缀 $[1, i]$ 可以表示成树上的一个节点，即从根节点走到对应节点 $u$ 的过程，并且 $|S_{1, i}|$ 等于其深度。

$S_{1, i}^{-1}$ 表示逆过程，即从 $u$ 走回根节点的过程。

对于每一个子区间 $[l, r]$ 操作后的长度就等于 $[1, l - 1]$ 对应的节点走到 $[1, r]$ 对应节点的简单路径长度。

使用启发式合并查询简单路径长度为 $k$ 的点对即可。

注意字母表的大小是 $|\sum|$ 是 $10^9$ ，需要动态开点。

B 费米子通讯网络

合法方案等价于选择了一种排列，由 $i$ 连向 $p_i$ 。

设 $C_{i,j}$ 表示 $i$ 连向 $j$ 的有向边条数。

则有：

ans = \sum_p (-1)^k \prod_{i = 1}^{n}C_{i, p_i}

其中 $k$ 表示选择的排列形成了 $k$ 个环，代价为 $(-1)^k$ 。

定义交换操作：选了 $i$ 和 $j$ ，其中 $i \ne j$ ，交换 $p_i$ 和 $p_j$ 。

相当于对于一个排列交换两个元素。

我们可以交换 $n-k$ 次，使得排列变成 $n$ 个环，即每次交换多出一个环，代价乘一个 $-1$ 。

此时 $p_i = i$ ，排列是偶排列，且代价为 $(-1)^n$ 。

我们知道：一次交换操作会让排列的奇偶性改变。

这样排列的奇偶性和代价之间形成了双射。

故 $p$ 是偶排列时，代价等于 $(-1)^n$ ，是奇排列时，代价等于 $(-1)^n \times(-1)$ 。

恰好满足行列式的定义：

det(A) = \sum_p sgn(p) \prod_{i = 1} ^n A_{i, p_i}

其中 $sgn(p)$ 表示排列 $p$ 的符号， $p$ 为偶排列时，符号为 $+$ ，为奇排列时，符号为 $-$ 。

因此答案为：

ans = deg(C) \times(-1)^n

C 挑积木

方案数共有 $k^n$ 种，接下来考虑计算高度贡献和 $sum$ 。

将贡献和拆成每一位对答案的贡献，分别求和。

sum = \sum_{i = 1}^n \sum_{j = 1}^k j \times f_{i,j}

其中 $f_{i,j}$ 表示第 $i$ 位的值为 $j$ 对答案有贡献的方案数。

记 $l(i)$ 表示在 $[1, i - 1]$ 中高度小于等于 $a_i$ 的积木个数。

$L(i)$ 表示在 $[1, i - 1]$ 中高度大于 $a_i$ 的积木个数。

$R(i)$ 表示在 $[i + 1, n]$ 中高度大于 $a_i$ 的积木个数。

第 $i$ 位有贡献当且仅当 $l(i) < R(i)$ 。

由于有 $L(i) + l(i) = i - 1$ ，则条件等价于 $i \le L(i) + R(i)$ ，即数组中大于 $a_i$ 的积木个数大于等于 $i$ 。

则有：

\begin{aligned} f_{i, j} &= \sum_{c=i}^{n-1} \binom{n-1}{c} (k-j)^c j^{n-c-1} \\ sum &= \sum_{i=1}^n \sum_{j=1}^k j \sum_{c=i}^{n-1}\binom{n-1}{c} \times (k-j)^c \times j^{n-c-1}\\ &= \sum_{j=1}^k j \sum_{c=1}^{n-1}c\binom{n-1}{c} \times (k-j)^c \times j^{n-c-1}\\ &= \sum_{j=1}^k j \times (n-1)\times(k-j) \sum_{c=1}^{n-1}\binom{n-2}{c-1}\times(k-j)^{c-1}\times j^{n-c-1} \\ &= \sum_{j=1}^k j \times (n-1)\times(k-j) \times k^{n-2} \\ &= (n-1) \times k^{n-2} \sum_{j=1}^k kj - j^2 \\ &= (n-1) \times k^{n-2} \left[ \frac{k^2(k+1)}{2} - \frac{k(k+1)(2k+1)}{6} \right] \\ &= \frac{k^{n-1}(k^2-1)(n-1)}{6} \end{aligned}

最后除以方案数即可：

ans = \frac{sum}{k^n} = \frac{(k^2-1)(n-1)}{6k}

D 铁银银铜金铜银银铁

由于每个子串都是回文串，所以对于每个长度为 $2$ 的子串也是回文串，故题目要求等价于字符串每个字符均相同。

因此有：

ans = \max_{c\in \sum} n - cnt(c)

其中 $cnt(c)$ 表示字符 $c$ 在字符串中出现的次数。

E 树树菌的星形共振

若最终的树有 $k$ 个节点，它们能形成一个类五芒星图案，当且仅当 $gcd(k, 2) = 1$ 。

故 $k$ 只能是奇数。

设这 $k$ 个节点权值为 $x$ ，则有 $\oplus_{i=1}^k x = x$ ，其中 $\oplus$ 表示异或操作。

题目中的合并操作并不会改变被合并部分的异或和。

故 $x$ 等于 $\sum_{i=1}^n a_i$ 。

考虑贪心。

对于一个以 $u$ 为根的子树，如果它的异或和等于 $x$ ，直接切开 $u$ 与 $u$ 父亲之间的连边即可。

但这样切最终可能会出现偶数个节点。

这种情况出现当且仅当整棵树的异或和是 $0$ 。

也就是切出来偶数个权值为 $0$ 的节点，只需要多合并掉一个即可。

F yourdestroy

这种问题直接求解一般都是很困难的数学问题，所以考虑二分然后判定（显然半径越大越好）

对于一个半径 $r$ ，先求出对于一对相邻的车来说，哪些时间段是合法的，由于不同的车发车间隔时间一样，所以只需要考虑前 $2$ 个车。

当两个车都在线段上沿直线运动时（没拐弯），用相对运动来看这个问题，把一个车视为不动，那么另外一个车的运动就是两个向量相加，也是一个直线运动。所以对于不动的车来说，另外一个车的运动轨迹就是一个线段，想求出二者距离小于等于 $r$ 的时刻，可以视为一个圆和线段相交的问题。

类似于双指针的思路，同时移动前 $2$ 个车，当其中一辆车走到站点时就说明要换方向了，这个时候分一次段。总共只有 $n$ 个点，所以时间段也是 $O(n)$ 个，对每个时间段分别求出距离小于等于 $r$ 的时间段。

此时我们得到了对于一对车来说若干个合法的时间段，要判断原问题是否合法。注意到对于 $2,3$ 来说，他们的合法片段实际就是把 $1,2$ 的往后平移（可以视为在时间轴上循环平移），比如说发车间隔是 $3$ ， $1,2$ 的合法时间是 $[2,4]$ ，那么 $2,3$ 的合法时间就是 $[5,7]$ 。

做一个变换，把时间轴切割成 $m$ 段然后堆到一起，只要有一个点被覆盖了 $m$ 次原问题就合法，并且被覆盖了 $m$ 次的点都是合法的时间点。

具体的做法就是按 $\text{mod } \frac Lm$ 处理一下区间，注意大区间可能会进行切割，然后对端点排序后，维护一个计数器 $tot$ ，遇到左端点 $+1$ ，遇到右端点 $-1$ ，只要最大值出现过 $m$ 就合法。

G A problem of tree

拆位，只考虑第 $i$ 位的贡献。

我们做树形 $dp$ ，设 $f_u$ 表示以 $u$ 为根节点的虚树个数， $tmp_{u,0/1}$ 表示以 $u$ 为根节点的所有虚树中的所有节点 $v$ 到 $u$ 节点的 $dis(u,v)$ 的值为 $0/1$ 的节点个数， $g_u$ 表示以 $u$ 为根节点的全部虚树的权值之和。

用类似树上背包的逻辑，设 $u$ 节点正在考虑儿子 $v$ 的贡献，记 $d(u,v)$ 表示 $u$ 到 $v$ 路径上边权和， $\oplus$ 为异或运算，方程易得

f'_u=f_u\times \sum_{x\in subtree(v)}(f_x+1) \\ tmp'_{u,0}=tmp_{u,0}\times \sum_{x\in subtree(v)}(f_x+1) +f_u\times\sum_{x\in subtree(v),d(x,u)\&{2^i}=op}tmp_{x,op} \\ tmp'_{u,1}=tmp_{u,1}\times \sum_{x\in subtree(v)}(f_x+1) +f_u\times\sum_{x\in subtree(v),d(x,u)\&{2^i}=op}tmp_{x,op\oplus1} \\ g'_u=g_u\times\sum_{x\in subtree(v)}(f_x+1)+f_u\times\sum_{x\in subtree(v)}g_x+tmp_{u,op1}\times\sum_{x\in subtree(v),d(x,u)\&{2^i}=op2}tmp_{x,op1\oplus op2\oplus 1}

现在的问题是我们需要快速计算 $\sum_{x\in subtree(v),d(x,u)\&{2^i}=0/1}tmp_{x,0/1}$ 。

考虑用 $dep_x$ 表示 $1$ 到 $x$ 的距离，这样 $d(x,u)=dep_x-dep_u$ ，考虑线段树合并，把 $tmp_x$ 全都插入到线段树上 $dep_x$ 的位置，这样在查询时，可以根据 $dep_u$ 的值在线段树上查找 $dep_x-dep_u$ 的第 $i$ 位为 $0/1$ 的全部 $x$ 了。

总复杂度 $O(n\log^2 V)$ 。

H 不协和音程

对于音高 $x$ ，存在合法路径当且仅当任意一对音高为 $x$ 的坐标 $(x_1, y_1)$ 和 $(x_2, y_2)$ ，其中 $x_1 \le x_2$ ，都有 $y_1 \le y_2$ 。

因此按 $x$ 排序后，只需要判定每一对相邻坐标是否满足 $y_1 \le y_2$ 即可。

一种可能的实现是：对每个音高 $x$ 存一个 $set$ ，动态维护每次插入和删除时相邻坐标 $y$ 的逆序个数即可。

I 唉，搞钱

当我们选了一个字符串后，其所有子串的代价都必须选。

符合最大权值闭合子图模型。

接下来考虑如何建模负权部分的图。

可以用 $gsam$ 维护本质不同的子串数量， $link$ 树具有非常好的图性质。

再将字符串节点向对应的每个前缀节点连一条 $inf$ 的边即可。

注意不要将 $trie$ 边也连进去，这样可能会导致图变得非常复杂，导致网络流的增广论数爆增从而 $TLE$ 。

J Yet Another Patchouli's Magical Problem

不妨设 $n > m$ ，此时 $min(n, m) = m$ 。

一种合法的方法是逐行依次放置。

(1, 1), (1, 2) ... (1, m), (2, 1), (2, 2) ... (n, m)

对于任意 $(i, j)$ 与 $(i, j + 1)$ 之间的负载：

$(i, j)$ 与 $(i, j + 1)$ 之间存在一条边，对间隔的负载是 $1$ 。
对于 $(i, x)$ ， $x \in [1, j]$ ，每个点与 $(i + 1, x)$ 相连，对间隔的负载为 $j$ 。
对于 $(i, x)$ ， $x \in [j + 1, m]$ ，每个点与 $(i - 1, x)$ 相连，对间隔的负载为 $m - j$ 。

因此一个负载间隔最大为 $1 + j + m - j = m + 1 \le m + 1$ 。

K The Eschatology of 0 and 1

对于每一个位置 $i$ ，多次进行同一种操作是无效的，故每种操作最多对 $i$ 进行一次。

设 $dp_{i, \{0, 1, 2, 3\}}$ 表示前 $i$ 个位置不进行操作/只进行第一种操作/只进行第二种操作/进行两种操作的最小花费。

则有转移方程：

当 $s_{i-1} \ne s_i$ 时：

\begin{aligned} dp_{i, 0} &= \min \left( dp_{i-1,1}, dp_{i-1, 2} \right) \\ dp_{i, 1} &= \min \left( dp_{i-1,0} + a, dp_{i-1, 3} + a \right) \\ dp_{i, 2} &= \min \left( dp_{i-1,0} + b+k, dp_{i-1, 3} + k \right) \\ dp_{i, 3} &= \min \left( dp_{i-1,1} + a+b+k, dp_{i-1, 2} + a+k \right) \end{aligned}

当 $s_{i-1} = s_i$ 时：

\begin{aligned} dp_{i, 0} &= \min \left( dp_{i-1,0}, dp_{i-1, 3} \right) \\ dp_{i, 1} &= \min \left( dp_{i-1,1} + a, dp_{i-1, 2} + a \right) \\ dp_{i, 2} &= \min \left( dp_{i-1,1} + b+k, dp_{i-1, 2} + k \right) \\ dp_{i, 3} &= \min \left( dp_{i-1,0} + a+b+k, dp_{i-1, 3} + a+k \right) \end{aligned}

对 $dp_{n, \{0,1,2,3\}}$ 取最小值即可。

L 结束乐队 × 无刺有刺 · 联合 Live 前的交流会

在无向图中，

\mathrm{dist}_G(u,v)=2 \iff (u,v)\notin E(G)\ \land\ \exists w:\ (u,w)\in E(G),(v,w)\in E(G).

考虑枚举中间点 $w$ ，令 $S=N(w)$ 为其邻居集合。对任意 $u,v\in S$ ：

若 $(u,v)\in E(G)$ ，则 $\mathrm{dist}_G(u,v)=1$ ，不应在 $H$ 中连边；
若 $(u,v)\notin E(G)$ ，则 $u-w-v$ 给出长度为 $2$ 的路且不为 $1$ ，因此 $\mathrm{dist}_G(u,v)=2$ ，应在 $H$ 中连边。

可知，点集 $S$ 在 $H$ 中诱导出的边恰好是导出子图 $G[S]$ 的补图 $\overline{G[S]}$ 的边。我们只需对每个 $w$ 求出 $\overline{G[S]}$ 的连通块，并将同一连通块内的点在全局并查集内合并；处理完所有 $w$ 后，并查集的连通块即为 $H$ 的连通块。

流程大致如下：

枚举中间点 $w$ ，令 $S=N(w)$ ，即 $w$ 的邻居集合。
构造导出子图 $G[S]$ 的边。暴力枚举 $S$ 内点对则为 $O(\sum \deg^2)$ ，最坏可达 $O(nm)$ 。考虑采用度数定向，将每条无向边 $(u,v)$ 定向为度数小的一端指向度数大的一端。设定向后出度为 $\mathrm{outdeg}(\cdot)$ 。由以下引理可得 $\max \mathrm{outdeg}(u)\le \sqrt{2m}$ ：

若 $\mathrm{outdeg}(u)=d$ ，则 $u$ 至少有 $d$ 个邻居度数 $\ge d$ ，从而总度数 $\sum\deg \ge d^2\le 2m$ ，故 $d\le \sqrt{2m}$ 。

因此对固定 $w$ ，对每个 $u\in S$ 只需遍历 $u$ 的出边 $u\to v$ ，若 $v\in S$ 则得到一条 $G[S]$ 内部边。
求补图 $\overline{G[S]}$ 的连通块。

维护仅包含 $S$ 内未访问点的双向链表 unvis。每次弹出点 $u$ 时，先标记其在 $G[S]$ 中的邻居集合（这些点在补图中与 $u$ 无边），然后遍历链表，将未被标记的点移出链表并加入 $\text{BFS}$ 队列，同时在并查集中合并。
全局维护并查集，累积合并所有 $w$ 的局部补图连通性，最终统计连通块大小。

复杂度方面：

构造所有 $G[N(w)]$ 的内部边： 总枚举量为
$\sum_w\sum_{u\in N(w)} \mathrm{outdeg}(u) =\sum_u \deg(u)\,\mathrm{outdeg}(u) \le \sqrt{2m}\sum_u \deg(u) =O(m\sqrt m).$
补图 BFS： 固定 $w$ ，设 $S=N(w)$ 。补图 BFS 维护 unvis 链表，仅包含尚未访问的点。每次队首为 $u$ 时，扫描 unvis：若某点 $v$ 未被标记为邻居，则将其从链表删除并入队；否则跳过。

删除操作每个点最多进行一次，贡献 $O(|S|)$ ；而对固定 $u$ ，被跳过的点必为 $u$ 在 $G[S]$ 中的邻居，跳过次数为 $\deg_{G[S]}(u)$ 。因此所有跳过次数至多为 $\sum_{u\in S}\deg_{G[S]}(u)=2|E(G[S])|$ 。

对所有 $w$ 求和， $\sum_w |N(w)| = 2m$ ，且 $\sum_w |E(G[N(w)])|$ 等价于三角形数的常数倍，最坏为 $O(m\sqrt m)$ ，因此总复杂度仍为 $O(m\sqrt m)$ 。
并查集操作总次数与上述取点/合并同阶，均摊为 $O(m\alpha(n))$ ，不构成瓶颈。