Shannon’s Channel

总览#

A. 2090 病毒#

题意： 判断一个字符串是否为“梗语言”。梗语言的长度必须恰好为 $8$，第 $1,3,5,7$ 个字符为辅音，第 $2,4,6,8$ 个字符为元音。

思路： 模拟即可。先判断字符串长度是否为 $8$，再逐位检查字符。奇数位不能是 a、e、i、o、u，偶数位必须是这五个元音之一。任意条件不满足就输出 Well-Being，否则输出 Suspected Virus。

实现： 可以写一个函数判断字符是否为元音。注意题目中的位置从 $1$ 开始，而字符串下标通常从 $0$ 开始，因此下标为偶数的位置应该放辅音，下标为奇数的位置应该放元音。

复杂度： 单个字符串的时间复杂度为 $O(|s|)$，额外空间复杂度为 $O(1)$。

C. 大鱼吃小鱼#

题意： 初始网格中全是障碍。操作一会在一个空位置加入一条鱼，新鱼的大小不小于此前加入的所有鱼，并询问它最多能吃多少条鱼。操作二允许把一条已有鱼的初始大小增加，询问为了吃完整个可达区域，最少需要增加多少。

思路：

因为新加入的鱼不小于此前的所有鱼，所以只要相邻位置已经有鱼，新鱼就一定能吃完整个相邻连通块。加入一条鱼时，将它与上下左右的已有连通块合并，操作一的答案就是合并后连通块大小减一。

普通的按秩合并会破坏合并发生的先后关系，因此每次都让新鱼成为根，把相邻旧连通块的根接到它下面。这样形成的父子关系与 Kruskal 重构树类似，但不需要显式建立一棵额外的树。

考虑旧连通块的根 r。它代表的连通块大小为 sz[r]，新加入的鱼大小为 v。若选中的鱼初始大小为 S，吃完整个旧连通块后，它的大小会变成：

要继续向上吃掉大小为 v 的新鱼，需要满足：

所以从 r 合并到新根时产生的门槛为：

将这个门槛记录在 tag[r] 中。对于任意一条原有的鱼，要一路吃到当前连通块的根，就必须满足路径上的所有门槛。因此 mx[x] 维护从 x 到当前根的最大门槛，路径压缩时同步取最大值即可。

操作二查询位置 x 时，先通过 find(x) 更新 mx[x]。若这条鱼原本的大小为 val[x]，最小增加量就是：

实现：

• fa 表示重构树意义下的父节点；
• sz 表示当前根所代表的连通块大小；
• tag 表示当前节点到父节点这次合并产生的门槛；
• mx 表示从当前节点到根的最大门槛；
• val 保存每条鱼的初始大小；
• act 记录格子中是否已经放入鱼；
• l 保存上一次操作的答案，用于解密坐标。

加入新鱼时，先找出四个方向上已经存在的鱼，并对相邻连通块的根去重。对于每个旧根 r，先把 sz[r] 加到新根的 sz 中，再令 tag[r] = v - sz[r] + 1、fa[r] = 新根。不能使用按秩合并，因为这里的父子方向本身就包含门槛信息。

复杂度： 每次操作只检查至多四个相邻格子，并进行常数次并查集操作，均摊时间复杂度为 $O(\alpha(nm))$，空间复杂度为 $O(nm)$。

E. 排列求值#

题意： 给定一个 $0$ 到 $n-1$ 的排列 $P$，计算：

思路： 直接枚举所有数对的复杂度是 $O(n^2)$。可以改为分别计算每个位置对答案的贡献。

对于下标从 $0$ 开始的 $P_i$，它作为右端点出现 $i$ 次，每次贡献 $+P_i$；作为左端点出现 $n-1-i$ 次，每次贡献 $-P_i$。因此 $P_i$ 的总贡献为：

最终只需要计算：

实现： 从左到右遍历排列，累加每个位置的贡献。答案可能为负，使用 long long 保存。

复杂度： 时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

F. 排列生成#

题意： 给定排列 $P$ 以及 $k,x$，构造另一个排列 $P'$，使得 $P'_k=x$，并且 $f(P')\equiv f(P)\pmod n$。

思路： 将排列中的每个数在模 $n$ 意义下平移相同的距离。

令：

然后构造：

所有数同时循环平移后，结果仍然是 $0$ 到 $n-1$ 的排列，并且显然有 $P'_k=x$。

对于任意一对位置 $i<j$，$P'_j-P'_i$ 与 $P_j-P_i$ 只可能相差 $n$ 的整数倍。因此每一项在模 $n$ 意义下都不变，整个排列的权值也满足：

所以该题总是有解，不需要输出 -1。

实现： 求出平移量 d，遍历原排列并输出 (P[i] + d) % n。

复杂度： 时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$（不计输出）。

G. 精度误差？！#

题意： 构造不超过 $2n+2$ 个三维点，使每个点恰好有 $n$ 个其他点与它的距离落在 $(1-\epsilon,1+\epsilon)$ 内，其中 $\epsilon=0.01$；任意两个不同点之间的距离还必须严格大于 $\epsilon$。

思路： 看起来是一道三维几何构造题，实际上是利用误差范围的诈骗题。构造两个完全相同的平面点阵，两层的高度差为 $1$。让同层的点彼此靠近，但距离严格大于 $\epsilon$，这样每个点与另一层的所有点距离都约为 $1$。

具体地，从一个 $10\times 10$ 的网格中依次取前 $n$ 个点，网格间距，也就是每个小格的边长，取 0.011。第一层放在 $z=0$，第二层复制相同的横纵坐标并放在 $z=1$，总共输出 $2n$ 个点。

同层最近两点的距离为 $0.011>0.01$。整个点阵的宽和高最多为：

所以两层任意两点之间的距离至多为：

同时，同层最远距离不超过 $0.099\sqrt 2$，远小于 $0.99$，不会被误判为距离约等于 $1$。因此每个点恰好与另一层的全部 $n$ 个点相邻，满足要求。

实现： 第 i 个点的横坐标取 0.011 * (i % 10)，纵坐标取 0.011 * (i / 10)，分别在 z = 0 和 z = 1 输出一次。使用足够的小数位数输出即可。

复杂度： 每组数据输出 $2n$ 个点，时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

复盘#

赛时只通过了 A、E。

F 的整体平移构造其实并不难，但比赛时没有想到。G 容易被三维几何的题面吓住，本质上只是利用 epsilon 构造两层小网格。C 赛时没有读到，赛后补题时才理清并查集上门槛的含义。

J 是大模拟，没有补；L 需要 AC 自动机，也暂时放弃。后面还是要补一下构造题的思维，以及复杂字符串算法的实现能力。