题解 - 2026 杭电春季联赛 (6)

1003

按照题意模拟即可，复杂度 $O(1)$。

1005

由于出现连续 $k$ 个相等元素后它们就会消失，我们不妨认为消失的就是最靠左的 $k$ 个元素。

考虑用栈维护这一操作，栈中存储这个元素的值和它的连续出现次数，一旦出现次数到达 $k$ 就弹出。

这样维护的每一次删除操作都是合法的，并且最终所有的元素都不会出现连续 $k$ 个。

这里还有一个问题，就是一个序列无论以何种顺序进行删除，最终的序列是否唯一？

考虑使用数学归纳法来证明，当长度 $<k$ 时或不存在连续 $k$ 个相等元素时显然成立。

假设序列 $S$ 的第一步有两种不相同的删除：

1. 若删除区间不相交，那么 $S=Ax^kBy^kC$，其中 $B$ 可能为空，设 $S_1=ABy^kC,S_2=Ax^kBC$。

   根据归纳假设，$S_1,S_2$ 无论以何种顺序进行删除，最终的序列是唯一的。

   那么 $S_1\to ABC$ 是合法的，$S_2\to ABC$ 也是合法的。

   因此 $S_1$ 的最终态等于 $ABC$ 的最终态；$S_2$ 的最终态也等于 $ABC$ 的最终态。

2. 若删除区间相交，这两个区间对应值必然相等，显然删除一步后到达的序列相等，那么根据归纳假设最终的序列是唯一的。

因此我们可以用开头提到的方法 $O(n)$ 求出最终序列。

1007

枚举 $A$ 在删除若干元素之后，长度为 $m$ 的连续子段的最后一个位置 $i$。

那么在以 $i$ 结尾、包含了 $1\sim m$ 的最小的区间之外，其它位置的元素都是没有必要被删除的。

因此这里的答案就是 $\min_i\{i-l_i+1-m\}$，其中 $l_i$ 是以 $i$ 结尾、包含了 $1\sim m$ 的最小区间的左端点。

可以记录 $1\sim m$ 每一个元素最后一次出现的位置 $p_1\sim p_m$，那么 $l_i= \min_{1\le j\le m} p_j$。

可以用 set 支持动态增删查最小值，复杂度 $O(n\log m)$。

1002

预处理好一个骰子通过旋转能达到的状态，然后 BFS 即可，复杂度 $O(Knm)$，其中 $K$ 是骰子的状态数。

1009

设给定的 $m$ 个无向边是特殊边，假设一条路径依次经过了 $e_1,e_2,\dots, e_k$，其中 $e_i=(x_i,y_i,w_i)$。

我们总可以认为 $a\leadsto b$ 不经过特殊边的权值是 $a\oplus b$：

1. 当 $a=b$ 时，权值是 $0$；
2. 当 $a\neq b$ 时，假设 $a\leadsto b$ 的路径是 $(v_1,v_2,\dots, v_p)$，其中 $v_1=a,v_p=b$，那么权值是 $(v_1\oplus v_2) \oplus (v_2\oplus v_3) \oplus \dots \oplus (v_{p-1}\oplus v_p)=a\oplus b$。

所以这个路径最终的权值是 $1\oplus (x_1\oplus w_1\oplus y_1) \oplus (x_2\oplus w_2\oplus y_2)\dots\oplus y_k\oplus n=1\oplus n\oplus \left(\bigoplus_{i=1}^k (x_i\oplus w_i\oplus y_i)\right)$。

由于无论以何种顺序经过任意的特殊边，总是存在路径的，于是我们把 $x_i\oplus w_i\oplus y_i$ 均插入线性基，查询这个线性基中元素与 $1\oplus n$ 异或的最大值即可，复杂度 $O(n\log V)$。

1004

求两点 $S,T$ 不经过凸包的最短路径，可以认为一定要走这个凸包和 $S,T$ 构成的新凸包上的边，如果 $S,T$ 其中一个点不在这个新凸包上，说明 $ST$ 不与凸包相交，答案就是 $|ST|$；否则，求出 $S\leadsto T$ 的顺时针和逆时针长度即可，参考类似题目 CCPC 2021 Guangzhou L。

复杂度 $O(Q\log N)$。

1008

这是一个结论，类似地结论也在 CF141E 中出现，即对于一个 $0,1$ 边权的无向连通图，定义生成树的权值是边权之和，那么权值为最小生成树和最大生成树之间的生成树都是存在的，特判不连通情况。

下面给出一个证明：

假设存在两个生成树的边集是 $A,B$，设 $w(A)$ 表示 $A$ 的边权之和，考察 $A\setminus B$：

1. 若 $A\setminus B=\varnothing$，说明 $\forall x\in A,x\in B$，那么 $A\subseteq B$；又因为 $|A|=|B|$ 所以 $A=B$。

2. 否则，设 $e\in A\setminus B$，将 $e$ 加入 $B$ 后一定恰好形成一个简单环。

   设这个环上的边为 $C$，既然 $e\in A$，一定 $\exists c\in C,c\neq e, c\not\in A$，否则 $A$ 中存在环。

   那么选出一个这样的 $c$，将 $e$ 加入 $B$ 后将 $c$ 删掉，形成的 $B'$ 仍然是一个合法的生成树，$A\setminus B'$ 中严格减少了一个元素。

   重复这样的过程，一定可以从 $B$ 到达 $A$，而每一次都是加入一条边、删除一条边，所以 $w(B')-w(B)=w_c-w_e\in \{-1,0,1\}$。

   既然每一个变化的绝对值最大是 $1$，那么在整数意义下是连续变化的，因此权值为最小生成树和最大生成树之间的生成树都存在。

因此只需要求出最小和最大生成树即可，复杂度 $O(n\log n)$。

1006

先给出一个结论，如果存在一个合法的括号路径，那么合法的最短路径的长度不会超过 $4n$。

把左括号看成 $+1$，右括号看成 $-1$，那么一个合法的括号路径是边权前缀和均非负，且边权和为 $0$ 的路径。

既然最短路径长度 $\le 4n$，那么 $+1$ 的边 $\le 2n$，于是前缀和的最大值 $\le 2n$。

因此可以把前缀和与点绑定，建一个分层图，那么这个图中有 $O(n^2)$ 个点，$O(nm)$ 条边，由于 $n,m$ 数量级相同，认为一次 BFS 是 $O(n^2)$ 的，那么对 $n$ 个点进行 BFS 是 $O(n^3)$ 的。

只需要预处理出答案后对每个询问 $O(1)$ 回答即可。

如何证明？考虑构造出一条长度不超过 $4n$ 的合法路径。

若 $a\leadsto b$ 的合法路径存在，那么 $a$ 一定有一条 $+1$ 的邻边，$b$ 一定有一条 $-1$ 的邻边。否则，$a$ 如何走都是 $-1$，或者必须经过 $+1$ 到 $b$ 才让边权和为零，则最后一步的前缀和是 $-1$，都是不合法的情况。

除此之外，$a\leadsto b$ 的合法路径 $W$ 存在，这个合法路径的边数一定是偶数：因为 $+1$ 和 $-1$ 的边数相等。

既然存在一个偶数路径，就可以把每一个点 $u$ 拆成 $u_0$ 和 $u_1$，那么起点是 $a_0$，终点是 $b_0$，要求中间每一条边都必须从 $u_0\to v_1$ 或者 $u_1\to v_0$。

在这个新的图中，我们把 $W$ 的环都删掉，这样这个路径剩下的点 $\le 2n$，那么边 $\le 2n-1$，并且保证边数仍然为偶数，那么边数 $\le 2n-1$。

记处理之后的路径为 $W'$，边权前缀和为 $S_0,S_1,\dots, S_k$，并且 $S_0=S_k=0$，$k$ 是路径的边数，是偶数，并且 $k\le 2n-2$。

既然 $a$ 一定有一条 $+1$ 的邻边，那么我们可以先让 $a$ 反复走这一条边 $x=2\left\lceil-\min\cfrac{S_i}{2}\right\rceil$ 次，这样能够保证路径每一个前缀和非负；并且让结束之前反复走 $-1$ 的邻边，那么就可以让最后反复走 $y=x+S_k$ 次， 保证最后的边权和为 $0$。

那么这个新路径 $W''$ 的长度是 $x+y+k=4\left\lceil-\min \cfrac{S_i}{2}\right\rceil+S_k+k\le k+2+S_k-2\min S_i$。

因为 $S_k-\min S_i+0-\min S_i\le (k-j)+j= k$，其中 $j$ 是 $S_i$ 取到最小值的下标。

于是长度 $\le 2k+2\le 4n-2$，也就是说，我们构造出了一个长度 $\le 4n-2$ 的合法路径，这证明了开头的结论。

1010

本题核心思路是利用 $\chi_s(x)=(-1)^{\operatorname{popcnt}(s\land x)}$ 的性质，下设 $W=2^m$，并且所有值都在 $[0,W)\cap \mathbb Z$ 中。

1. $\frac{1}{W}\sum_{s=0}^{W-1} \chi_s(x)=[x=0]$

   证明如下：

   • 当 $x=0$ 时，$(-1)^0=1$ 恒成立，因此这个式子等于 $1$；

   • 当 $x\neq 0$ 时，只看 $x$ 的二进制位为 $1$ 的那些位，设有 $y$ 个。把其余位相同的放到同一组来求和，那么共有 $2^{m-y}$ 组。

     $$\frac{1}{W}\sum_{s=0}^{W-1} \chi_s(x)=2^{m-y}\frac{1}{W} \sum_{i=0}^y (-1)^i \binom{y}{i}=0$$

2. $\forall 0\le x,y<W, \chi_s(x\oplus y)=\chi_s(x)\chi_s(y)$

   证明如下：

   设 $x_0,x_1,\dots,x_{m-1}$ 是 $x$ 的每一个二进制位 $y_0,y_1,\dots,y_{m-1}$ 是 $y$ 的每一个二进制位。

   根据定义有 $\chi_s(x)=\prod_{i=0}^{m-1} \chi_s(2^ix_i)$，并且 $\chi_s(0)=1,\chi_s(2^i)=(-1)^{[s_i=1]}$。

   考虑 $\chi_s(x_i)\chi_s(y_i)$，若 $x_i=y_i$，那么 $\chi_s(x_i)\chi_s(y_i)=1$；否则，必然有一个 $1$ 一个 $0$，那么 $\chi_s(x_i)\chi_s(y_i)=(-1)^{[s_i=1]}$。

   因此 $\chi_s(x\oplus y)=\chi_s(x)\chi_s(y)$。

设 $n_k$ 是在 $1\sim n$ 中无顺序选 $k$ 个数组成的所有集合，那么可以化简目标式：

$$\begin{aligned} \sum_{I\in n_k} \left[\bigoplus_{i\in I} a_i=0\right] &=\sum_{I\in n_k} \frac{1}{W}\sum_{s=0}^{W-1} \chi_s\left(\bigoplus_{i\in I} a_i\right)\\ &=\frac{1}{W}\sum_{s=0}^{W-1}\left(\sum_{I\in n_k}\prod_{i\in I} \chi_s(a_i)\right) \end{aligned}$$

对于 $n$ 个元素无序选择 $k$ 个，并把对应权值乘起来再相加，这与形式幂级数关系很大，所以往这方面考虑：

$$\frac{1}{W}\sum_{s=0}^{W-1}\left(\sum_{I\in n_k}\prod_{i\in I} \chi_s(a_i)\right)=\frac{1}{W}\sum_{s=0}^{W-1} [z^k]\left(\prod_{i=1}^n(1+\chi_s(a_i)z)\right)$$

由于 $\chi_s(x)$ 的值只有 $1$ 和 $-1$，所以关键问题就是如何求出 $1$ 和 $-1$ 的数量，设为 $p_s,q_s$。

显然有 $p_s+q_s=n$，那么只需要考虑再找到一个方程。

由于 $p_s-q_s=\sum_{i=1}^n \chi_s(a_i)=\sum_{j=0}^{W-1} c_j\chi_s(j)$，其中 $c_j$ 表示 $j$ 在 $a_1\sim a_n$ 中的出现次数，那么所有的 $p_s-q_s$ 可以通过对 $c$ 进行一次 FWT 在 $O(W\log W)$ 求出。

所以可以对式子进行进一步转化：

$$\begin{aligned} \frac{1}{W}\sum_{s=0}^{W-1} [z^k]\left(\prod_{i=1}^n(1+\chi_s(a_i)z)\right) &=\frac{1}{W}\sum_{s=0}^{W-1} [z^k](1+z)^{p_s}(1-z)^{q_s}\\ &=\frac{1}{W}\sum_{s=0}^{W-1} \sum_{i=0}^k \binom{p_s}{i}\binom{q_s}{k-i}(-1)^{k-i} \end{aligned}$$

这是可以 $O(kW)$ 求出的。

1001

首先，把连通块看成一个点，那么就是需要把这 $n-m$ 个连通块用 $n-m-1$ 条边连起来。

对于一个连通块来说，全局树的直径要么一个连通块内部的距离，要么是两个连通块之间的点的距离。

如果是两个连通块之间的点，考虑如下的方案：对于每一个连通块，我们只选择使得 $\max_u d_{u,v}$ 最小的 $v$，并且设这个连通块 $i$ 的半径为这个值，记做 $r_i$。

这样做有两个好处，首先，它能让两个连通块之间的点这一路径的两端极端情况最好；其次，它能让中间经过的别的连通块不会产生除了我们添加的边以外的贡献。

所以这个方案是一定比其它方案更优的，但是到这一步仍然没有办法继续做下去。

取 $r_i$ 最大的 $i$ 为根，记作 $1$，观察这个缩点之后的树的形态，设每一个点到父亲的边边权为 $p_i$。

对于这个树的任意两个点 $u,v$：

1. 如果是 $u$ 是 $v$ 的祖先，那么 $u,v$ 对答案的贡献 $c_{u,v}=r_u+r_v+d_{u,v}\le r_v+r_1+d_{u,1}$，所以 $u,v$ 一定不优于 $u,1$ 的贡献。
2. 如果 $v$ 是 $u$ 的祖先情况也类似；
3. 如果都不是，那么 $c_{u,v}=r_u+r_v+d_{u,v}\ge r_u+r_v+p_u+p_v$。

综上，我们可以认为根为 $1$ 的菊花图总是比其它形态的树更优，因为菊花图能够保证 $u,1$ 的贡献更小，并且任意两个非根点的贡献也更小。

那么现在的问题就变成了，给定 $r_1,r_2,\dots, r_k$，其中 $k\ge 2$ 并且 $r_1=\max_{1\le i\le k} r_i$。

我们需要分配一个正整数序列 $p_2,\dots,p_k$ 满足 $\sum_{i=2}^k p_i\ge S$ 并且 $\max\{D_0,p_i+r_i+r_1,p_i+p_j+r_i+r_j\}$ 最小，其中 $D_0$ 是原连通块内部的点的最大距离。

考虑二分答案 $M$，那么我们只需要求出当 $\forall 2\le i\le k,p_i+r_i+r_1\le M$， $\forall {2\le i\neq j\le k}, p_i+p_j+r_i+r_j\le M$，$\forall 2\le i\le k,p_i\ge 1$ 同时成立时，$\sum_{i=2}^k p_i$ 的最大值即可。

为了方便，我们令 $w_i=p_i+r_i$，由于 $r_i$ 是定值，所以 $\sum p_i$ 最大当且仅当 $\sum w_i$ 最大。

1. 若 $2(M-r_1)\le M$，等价于 $r_1\ge \lceil M/2\rceil$说明所有的 $w_i$ 都可以取到第一个限制的上界，那么就让它取到；

2. 否则，有 $r_1<\lceil M/2\rceil$，如果有 $k\ge 3$ 的话，就应该考虑第二个限制。

   第二个限制实际上只关系 $w$ 的最大值和次大值，所以我们可以认为有一个最大值，其余 $k-1$ 个均为次大值，这样既能让 $\sum w_i$ 变大，也能尽可能满足 $w_i\ge p_i+1$ 的限制。

   考虑到最大值减小 $1$，次大值增加 $1$，$\sum_{i=1}^k w_i$ 一定不会减小，并且 $w_i\ge p_i+1$ 的限制除了最大值以外都会变宽，所以能减小一定会尽量减小。

   也就是说，$w$ 的最大值 $w_1$ 最终会减小到 $\max\{\lceil M / 2\rceil, r_1+1\}$，次大值自然就是 $M-w_1$。

   如果这样都无法满足所有 $w_i\ge p_i+1$ 的限制，说明别的情况更不可能满足限制，直接报告无解。

所以综合下来前面预处理 $r$ 的值复杂度 $O(n)$，后面二分答案并检查是 $O(\log V)$ 的。