Shannon’s Channel

总览#

A. AUS#

题意： 给定三个由小写字母组成的字符串 $S_1,S_2,S_3$，判断是否存在一种字符映射 $F$，使得 $F(S_1)=F(S_2)\ne F(S_3)$。每个字母映射为一个字母，不同字母可以映射到同一个字母。

思路：

先根据三个字符串的长度进行特判：

1. 若 $|S_1|\ne |S_2|$，由于字符映射不会改变字符串长度，前两个字符串不可能映射为同一个字符串，答案为 NO。
2. 否则，若 $|S_2|\ne |S_3|$，可以将所有字母映射为同一个字母，使前两个字符串相等；第三个字符串由于长度不同，一定与它们不同，答案为 YES。

接下来只需考虑三个字符串等长的情况。对 $26$ 个字母建立并查集，逐位合并 $S_1[i]$ 和 $S_2[i]$。为了让前两个字符串映射后相等，这些对应位置上的字母必须映射为同一个字母；通过等价关系的传递，同一集合中的所有字母都必须映射为相同字母。

完成合并后，逐位检查 $S_2[i]$ 和 $S_3[i]$ 是否属于同一个集合：

• 若所有位置的两个字母都属于同一集合，那么任何满足 $F(S_1)=F(S_2)$ 的映射都会使 $F(S_2)=F(S_3)$，无法区分，答案为 NO。
• 若存在一个位置的两个字母属于不同集合，就让不同集合映射为不同字母。集合至多有 $26$ 个，因此这样的映射一定可以构造出来，并且该位置映射后不同，答案为 YES。

实现： 使用带路径压缩的并查集维护字母之间的等价关系。先扫描 $S_1,S_2$ 合并对应字母，再扫描 $S_2,S_3$，判断是否存在所属集合不同的位置。

复杂度： 时间复杂度为 $O(L)$，其中 $L$ 为三个字符串的总长度，主要来自扫描字符串并合并、查询字母的所属集合。

E. Elevator II#

题意： 有 $n$ 个人等待乘坐电梯，第 $i$ 个人要从 $l_i$ 层到 $r_i$ 层，其中 $l_i<r_i$。电梯同时只能运送一个人，初始位于 $f$ 层。向上移动一层消耗 $1$ 单位电量，向下移动不耗电。求运送所有人的最小总耗电量，并输出一种最优的运送顺序。

思路：

每个人都必须从 $l_i$ 被送到 $r_i$，所以载人上升的代价是固定的：

将它作为基准值后，只需要最小化额外的空载上升代价。

先按 $r_i$ 从大到小排序，取排在第一位的乘客，其起点记为 $l_1$。若初始楼层 $f\ge l_1$，就可以不花额外电量到达他的起点，送完后电梯到达最大的终点。接下来继续按终点从大到小运送：当前楼层不低于下一位乘客的终点，更不低于他的起点，因此接人只需下降，不会产生空载上升。此时额外代价为 $0$，总耗电量恰好为基准值，一定最优。

若 $f<l_1$，就先想办法到达不低于 $l_1$ 的楼层，再执行上述顺序。在上升过程中，可以提前运送一些乘客，用他们的载人行程覆盖这段上升。这里的上升已经计入基准值，不需要额外付费。

为此，再将所有乘客按 $l_i$ 从小到大排序，维护当前楼层 curf，初始为 $f$。依次扫描乘客：

1. 若 $r_i\le\text{curf}$，这位乘客不能帮助电梯继续上升，暂时跳过。
2. 若当前仍有 $\text{curf}<l_1$，就运送这位乘客。到达起点的额外代价为 $\max(l_i-\text{curf},0)$，随后电梯到达 $r_i$，令 curf 更新为 $r_i$，记录他的编号并标记为已运送。
3. 一旦 $\text{curf}\ge l_1$，就不再提前运送乘客。将所有尚未运送的人按 $r_i$ 从大到小接在答案后面即可，后续不会产生额外代价。

按起点递增扫描的原因是：若下一位能帮助上升的乘客满足 $l_i>\text{curf}$，那么区间 $[\text{curf},l_i]$ 内没有乘客行程可以帮助继续上升。此前扫描过的乘客，要么已经运送，要么终点不超过当前楼层；之后的乘客起点又都不小于 $l_i$。这段空载上升因此无法避免。其余上升都由载人行程完成，所以算法只支付必要的额外代价。

实现： 保留两份乘客数组，分别按起点递增、终点递减排序。先计算基准值，再在起点递增的数组中构造提前运送的部分，用 vis[id] 标记已运送的乘客。最后扫描终点递减的数组，将未标记的编号依次加入答案。总耗电量使用 $64$ 位整数保存。

复杂度： 时间复杂度为 $O(n\log n)$，主要来自对乘客按起点和终点排序。

H. Heavy-light Decomposition#

题意： 给定 $n$ 个节点和 $k$ 条链，每条链由编号区间 $[l_i,r_i]$ 内的节点按顺序组成。构造一棵有根树，使它的某一种轻重链剖分结果恰好是这些链，输出每个节点的父亲，根节点的父亲为 $0$；若无解，输出 IMPOSSIBLE。重儿子指子树大小最大的儿子，大小相同时可以任选一个。

思路：

链内的父子关系已经确定，只需要决定各条链的链头接到哪里。将链长定义为节点个数 $r_i-l_i+1$，按长度从大到小排序，记最长链长为 $L$，最短链长为 $s$。

若只有一条链，直接将所有节点连成这条链即可。下面考虑至少两条链的情况。

先判断两种无解情况：

1. 所有链的长度都相等。
2. 最长链至少有两条，并且 $L-s=1$。

其余情况分为两类构造。

最长链只有一条：

选这条最长链的第一个节点作为根 root，将其余所有链的链头都接到 root 上。

根在主链上的儿子，其子树大小为 $L-1$；其余儿子的子树就是各自整条链，大小至多为 $L-1$。因此可以选择主链上的儿子作为重儿子。其他链内部都只有一个儿子，重边自然沿着原链延伸，剖分结果符合要求。

最长链至少有两条，且 $L-s\ge 2$：

任选一条最长链作为主链，将第一个节点记为 root，第二个节点记为 u2。把一条最短链的链头接到 u2 上，其余所有链的链头都接到 root 上。

这里必须接最短链，而不是再接一条最长链。构造后：

• 在 u2 处，主链后继的子树大小为 $L-2$，接入的最短链子树大小为 $s\le L-2$，所以仍可选择主链后继为重儿子。
• 在 root 处，u2 的子树大小为 $L-1+s\ge L$，其余儿子的子树大小至多为 $L$，所以仍可选择 u2 为重儿子。

其余节点没有额外分支，因此各条给定链都能保持为重链。子树大小相等时，选择主链方向即可。

实现： 按链长递减排序后，通过前两条链判断最长链是否唯一，通过首尾链判断最大、最小长度。链内统一令 ans[j] = j - 1，链头的父亲按上述分类设置，根的父亲保留为 $0$。只有一条链时，直接输出 $0,1,\ldots,n-1$。

复杂度： 时间复杂度为 $O(n+k\log k)$，来自对 $k$ 条链排序，以及构造、输出 $n$ 个节点的父亲。

K. Kind of Bingo#

题意： 给定一个 $n\times m$ 的网格和一个长度为 $nm$ 的操作序列。每次操作标记一个格子，每个格子恰好被标记一次。第一次出现某一整行都被标记时，已执行的操作次数记为 $b$。可以交换序列中任意两个操作，至多交换 $k$ 次，求 $b$ 的最小值。

思路：

将每个格子被标记的时间按行分组。按操作顺序读入时，把当前时间加入对应行的数组，因此每行的标记时间天然递增，不需要额外排序。

先考虑让某一行尽早被全部标记。设这一行的标记时间依次为 $p_1<p_2<\cdots<p_m$。不交换时，要等到 $p_m$ 才能完成这一行；至多交换 $k$ 次，就可以把最后的至多 $k$ 个标记操作换到前面。因此，当 $k<m$ 时，关键就是这一行第 $m-k$ 个标记的时间 $p_{m-k}$。

同时，每次操作只能标记一个格子，完成一行至少需要 $m$ 次操作，所以这一行最早完成的时间为

这个时间既是下界，也一定能够达到：令 $t=\max(m,p_{m-k})$，此时这一行至少已有 $m-k$ 个标记操作位于前 $t$ 次操作中，缺少的标记至多有 $k$ 个。由于 $t\ge m$，前 $t$ 个位置中属于其他行的操作足够多，可以逐个与缺少的标记交换，从而在不超过 $k$ 次交换后完成这一行。

枚举所有行，取第 $m-k$ 个标记时间的最小值，再与 $m$ 取最大值，就是最终答案。

若 $k\ge m$，则可以直接把任意一行的所有标记操作换到前 $m$ 个位置，答案为 $m$。

实现： 格子按行依次编号，从 $1$ 开始。读到第 $i$ 次操作标记编号为 $x$ 的格子时，将 $i$ 加入 pos[(x - 1) / m]。若 $k<m$，遍历每行的 pos[row][m - k - 1] 取最小值，最后与 $m$ 取最大值。这里数组下标从 $0$ 开始，所以第 $m-k$ 个元素对应下标 $m-k-1$。

复杂度： 时间复杂度为 $O(nm)$，主要来自读取并按行记录全部 $nm$ 次标记操作。

M. Make It Divisible#

题意： 给定一个正整数序列 $b$ 和整数 $k$。若一个连续子数组中存在某个元素能够整除该子数组的所有元素，就称这个子数组是好的。要求给所有元素统一加上 $x$ 后，每个连续子数组都是好的。求满足 $1\le x\le k$ 的合法 $x$ 的数量与总和。

思路：

首先特判所有元素都相等的情况。无论加上多少，所有元素仍然相等，每个区间都满足条件。因此 $1$ 到 $k$ 的所有整数都合法，数量为 $k$，总和为 $k(k+1)/2$。

下面考虑元素不全相等的情况。由于所有元素都是正数，一个区间中若有元素能整除所有元素，它一定就是区间最小值。因此题目等价于：每个区间的最小值加上 $x$ 后，都能整除该区间内的每个元素加上 $x$。

先用整个数组的条件缩小候选范围。记全局最小值为 $mn$，则 $mn+x$ 必须整除所有 $b_i+x$，从而也必须整除任意两个相邻元素之差。令

于是 $mn+x$ 必须是 $g$ 的正因数。分解 $g$ 并枚举它的所有正因数 $d$，令 $x=d-mn$，只保留 $1\le x\le k$ 的候选。注意，因数 $d$ 本身不是答案，减去全局最小值后才是候选 $x$。

但整个数组满足条件，并不代表每个区间都满足。为此，对原数组建立小根笛卡尔树：节点的中序顺序与数组下标一致，父亲的值不大于儿子的值。统一加上 $x$ 不改变元素之间的大小关系，所以所有候选都可以复用同一棵树。

对于每个候选 $x$，检查树上每条父子边。设父亲为 $u$、儿子为 $v$，要求

只要存在一条边不满足，就舍弃该候选；若所有边都满足，就将 $x$ 计入数量与总和。

正确性：

父子边条件是必要的：父亲与儿子两个下标之间的区间，最小值就是父亲的值，因此合法时父亲加 $x$ 必须整除儿子加 $x$。

它也是充分的：任意区间的最小值对应的节点，是该区间内所有节点的祖先。若每条父子边都满足整除关系，利用整除的传递性，这个最小值加 $x$ 就能整除区间内每个元素加 $x$。因此检查所有父子边，等价于检查所有区间。

实现： 先求最小值并特判全相等，再计算相邻差的 GCD。试除分解 $g$ 后，通过 DFS 枚举各质因子的指数，生成所有因数。使用单调栈在线性时间内建立笛卡尔树，只需记录每个节点的父亲；栈顶的值严格大于当前值时弹栈，相等时保留。每个候选遍历所有非根节点，检查其与父亲的整除关系即可，无需显式建立儿子数组。数量、总和及相关运算使用 $64$ 位整数。

复杂度： 时间复杂度为 $O(n\log n+\sqrt g+nD)$，其中 $D$ 为 $g$ 的正因数个数，三项分别来自数组排序、试除分解 $g$，以及对每个候选检查笛卡尔树的父子边。