Shannon’s Channel

总览#

K. D-Mail 机构代号#

题意： 给出若干院校名称。初始简称由每个单词的首字母拼成；若多个院校的简称相同，则从前往后把单词改为完整拼写，已经唯一的简称不再变化。求每所院校最终的简称。

思路： 直接模拟冲突的细化过程即可。

先用每个单词的首字母拼出初始简称。枚举每对院校；若初始简称不同，它们不可能冲突。否则，两个名称的单词数相同，且每个位置的首字母相同。于是从前往后寻找第一个完整单词不同的位置，并将这一位置及之前的单词标记为需要全拼。

首个不同单词也必须全拼：两校在该位置的首字母相同，若仍保留缩写就无法区分。实现时应当先把当前位置标记为 need，再判断完整单词是否不同并停止。某所院校可能与多所院校冲突，need 取所有冲突对要求的并集即可。

实现： 读入 n 后，cin.ignore() 吃掉行末换行；随后用 getline 读取每个完整校名。对每一行建立 istringstream，用 while (iss >> word) 逐个取出按空格分隔的单词。ana[i] 保存第 i 所院校的单词，need[i][k] 表示第 k 个单词是否输出全拼。

枚举院校对时，若 ans[i] == ans[j]，便从前向后执行：先令两边对应位置的 need 为真，再检查两个完整单词是否不同；不同则停止。最后按 need 输出完整单词或首字母。

复杂度： 设单词数最多为 $m$、单词长度最多为 $L$。时间复杂度为 $O(n^2mL)$，额外空间复杂度为 $O(nmL)$。

L. Bobo 的幸运取模#

题意： 统计有序正整数对 $(a,b)$ 的数量，满足 $1\le a,b\le n$ 且：

思路： 开始可以用 $O(n^2)$ 暴力枚举并打表找规律。可以观察到，当固定 $j=b$ 时，第一个合法的 $i=a$ 满足 $i\ge j^2$，所以只需枚举到 $\sqrt n$。接下来改为统计每个 $j$ 对答案的贡献，去掉对 $i$ 的枚举。

形式化地，令：

原条件等价于：

写成 $i=x+jt$。由于 $j\equiv-1\pmod{j+1}$，代入第二个同余式后有 $x-t\equiv x+1\pmod{j+1}$，所以 $t\equiv-1\pmod{j+1}$。因此所有解为：

当 $k=0$ 时，$i=x-j<0$；当 $k=1$ 时，$i=j^2+x>0$。之后随 $k$ 单调增加，所以所有正整数解恰好从 $k=1$ 开始。

记周期为：

每个长度为 $P$ 的周期中，先有连续 $j^2$ 个 $i$ 不满足条件，随后有连续 $j$ 个 $i$ 满足条件，即：

因此最小合法值为 $j^2$，只需枚举 $j^2\le n$。令 len = n - j * j，固定 j 的贡献为：

实现： 枚举 j = 1 到 j * j <= n，令 mod = j * j + j，直接按上式累加。n 可达 $10^{12}$，相关变量使用 long long。

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

G. 瞬、心心相印#

题意： 有 $n$ 个数，每种数值均出现偶数次。每轮对手选择两个未使用的数，玩家观察后将它们分别放到左右两侧。判断是否存在确定性策略，使无论对手如何选择，最终左右两侧元素和都相等。

思路： 手玩样例可以发现结论：存在必胜策略，当且仅当不同数值的个数不超过 $3$。

先证明四种或更多数值时一定无解。对手任选四个不同值 $A,B,C,D$，先给出 $(A,B)$ 与 $(C,D)$。设玩家放到左侧的是 $p,q$，右侧的是 $r,s$。对手再自适应地给出 $(p,q)$ 与 $(r,s)$。

前两轮后的差值为 $p+q-r-s$，后两轮的差值分别只能取 $\pm(p-q)$ 与 $\pm(r-s)$。四种选择的总差均可写为 $2(u-v)$，其中 $u\in\{p,q\}$、$v\in\{r,s\}$。四个数互不相同，所以总差不可能为零。其余数值全部按相同数对拆开即可，因此玩家不可能保证获胜。

当不同数值数不超过 $3$ 时，可以将相同数对拆到两侧，并让同类异值数对的方向交替；三种值时将三个可能的剩余异值对定向成环即可抵消。因此此时存在必胜策略。

实现： 只需统计不同数值的个数；不超过 $3$ 输出可行，否则输出不可行。

复杂度： 统计与构造均为 $O(n)$（若用有序映射统计则为 $O(n\log n)$），额外空间复杂度为 $O(n)$。

A. 入侵天使领域行动#

题意： 给定一个非负整数数组。一次操作选择一个非负整数 $k$，支付 $k$ 的代价，并任选若干数组元素与 $k$ 按位异或。求将数组变为非递减序列的最小总代价。

思路： 将一次操作的 k 拆成其中每个为 $1$ 的二进制位，总代价不变，而且不同位可以选择不同的元素集合。对于同一个二进制位，多次异或的元素集合取对称差后，可以合并为一次操作。因此每一位至多购买一次。

用掩码 $M$ 表示已经购买的位，总代价就是 $M$ 的数值。对任意一个 $a_i$，$M$ 中的位都能独立选择为 $0$ 或 $1$，而 $M$ 外的位不能改变。令：

其中 $r$ 的位都是固定位。当前数的所有可达值形如 $r\mathbin{|}x$，其中 $x\subseteq M$；最大可达值为 $r\mathbin{|}M$。

固定 $M$ 后，从左到右维护已经选出的前一个数 pre。若：

则连当前数的最大可达值都不够，$M$ 不可行。否则一定存在不小于 pre 的可达值。为了让后续限制尽量弱，需要把当前数取为不小于 pre 的最小可达值，并更新 pre。

构造这个最小值时，从高到低处理二进制位。固定位直接复制到 cur。对于自由位，先尝试让它为 $0$；设高位已经确定为 cur，再把所有低位尽量设为 $1$，得到当前位取 $0$ 时的最大补全值 mx。若 mx < pre，低位无法弥补当前位，当前位必须取 $1$；否则保留 $0$。最终的 cur 就是新的最小 pre。

接下来从高到低贪心构造答案 ans。处理第 $b$ 位时，暂时不购买它，并把所有尚未决定的低位都视作可购买：

这是第 $b$ 位为 $0$ 时自由位最多的候选。购买更多位只会扩大可达集合，不会让可行方案失效；因此若这个 $M$ 仍不可行，第 $b$ 位就一定必须加入 ans。反之可以确定第 $b$ 位为 $0$，继续处理更低位。

实现： 外层从第 $30$ 位向下枚举。对每个候选 M，从左到右检查所有 $a_i$；每个数再从高到低构造最小可达的 cur。注意外层的 M 始终不变，内层改变的是当前数的 cur，不是购买位集合。

复杂度： 设值域二进制位数为 $B$。外层枚举 $B$ 位，每次检查 $n$ 个数，每个数再扫描 $B$ 位，时间复杂度为 $O(nB^2)$，即 $O(n\log^2 V)$；额外空间复杂度为 $O(1)$。

H. 取模三元组#

题意： 将集合 $\{0,1,2,\ldots,3n-1\}$ 划分为 $n$ 个有序三元组 $(x_i,y_i,z_i)$。每个整数恰好出现一次，且满足 $z_i>0$、$x_i\bmod z_i=y_i$。输出任意一种构造。

思路： 不直接处理取模关系，而是主动构造更强的条件：

这样必然有 $x\bmod z=y$。问题于是变成：每次选择两个未使用的数 $y,z$，并让它们的和 $x$ 也恰好是一个未使用的数。

将数字按是否为 $3$ 的倍数分类。普通三元组中取一个 $3$ 的倍数 $a$ 和一个非 $3$ 倍数 $b$，它们的和 $a+b$ 仍然不是 $3$ 的倍数。于是每组正好使用一个 $3$ 的倍数与两个非 $3$ 倍数，和全集中 $n$ 个 $3$ 的倍数、$2n$ 个非 $3$ 倍数的数量关系吻合。

先输出特殊组：

它处理了 $0$、$1$ 与一个非 $3$ 倍数。对 $i=1,2,\ldots,n-1$，令：

输出：

后两项按大小放置，保证余数小于模数；第一项又恰为它们的和，所以每组合法。

$a_i$ 从大到小取遍剩余的 $3$ 的倍数。$b_i$ 的序列为 $2,4,5,7,8,\ldots$，即从小到大取非 $3$ 倍数；而：

依次得到 $3n-1,3n-2,3n-4,3n-5,\ldots$，恰好是从大到小的其余非 $3$ 倍数。特殊组中的第一个数正好是两段序列之间唯一剩下的非 $3$ 倍数，因此所有 $0$ 到 $3n-1$ 的数恰好各出现一次。

实现： 先输出 ((3 * n + 2) / 2, 0, 1)。随后枚举 i = 1 到 n - 1，计算 a = 3 * (n - i)、b = (3 * i + 2) / 2，输出 a + b、min(a, b)、max(a, b)。

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

复盘#

赛时通过了 K、L、G，赛后补了 A、H。

K 是字符串模拟，关键在于冲突时首个不同单词也要全拼；L 从暴力打表观察到阈值后转为按模周期统计贡献；G 则需要把手玩结论补成对手自适应选对的严格证明；A 需要先把按位操作归约成购买掩码，再利用可行性单调性做高位贪心；H 从 $x=y+z$ 出发，将取模条件转化为按 $3$ 的倍数分类并配对覆盖全集。