CWNU 算协挑战赛 Round 4 题解

A. 人人都在等 GTA 6

出题人：邓文韬

算法思路

令

$$q=\left\lfloor\frac{M}{N}\right\rfloor,\qquad r=M\bmod N.$$

每轮完整发放会给全部 $N$ 名同学各一份兑换码。前 $q$ 轮结束后，每名同学都获得 $q$ 份。

剩余 $r$ 份依次发给编号为 $1$ 到 $r$ 的同学。因此，前 $r$ 名同学输出 $q+1$，其余同学输出 $q$。

正确性证明

由带余除法，$M=qN+r$，且 $0\le r<N$。

前 $q$ 轮共发放 $qN$ 份，每名同学恰好得到 $q$ 份。余下 $r$ 份恰好由编号为 $1$ 到 $r$ 的同学各得到一份。因此，算法给出的每名同学所得数量与实际发放结果一致。

复杂度分析

输出 $N$ 行，时间复杂度为 $O(N)$，额外空间复杂度为 $O(1)$。

B. 整数报数

出题人：苟立军

算法思路

从 $A$ 到 $B$ 逐个枚举整数，输出前将字段宽度设为 $5$，并累计总和。

另维护已输出数量，每满 $5$ 个整数或到达 $B$ 时换行。循环结束后输出总和。

正确性证明

输出 $x$ 后，已经恰好按顺序输出 $A$ 至 $x$ 的每个整数一次，累计值等于它们之和。初始状态与每次累加均保持这一性质，因此枚举到 $B$ 后得到完整清单及正确总和。

换行只在计数为 $5$ 的倍数或到达最后一个整数时执行，且两个条件使用同一个判断，不会产生额外空白行。每次输出均重新设置字段宽度，满足右对齐要求。

复杂度分析

令 $N=B-A+1$，时间复杂度为 $O(N)$，额外空间复杂度为 $O(1)$。

C. 加法输入检查

出题人：苟立军

算法思路

使用整行读取保留所有空格，寻找第一个半角空格并分割。

对每个字段依次检查：

1. 字段非空。
2. 全部由数字组成。
3. 数值在 $[1,1000]$ 内。

数字累积时，一旦超过 $1000$，即可判定不合法，避免超长输入造成整数溢出。最后根据两个字段的合法性，分别输出数值或问号。

正确性证明

第一个空格的位置唯一，因此分割与题目定义一致，后续空格都保留在第二个字段中。逐字符检查能够排除所有含非数字字符的字段。

对全数字字段，按十进制累积得到其数值。若中途超过 $1000$，继续追加数字只会使其仍然超过上限，所以提前拒绝是正确的。累积完成后再检查数值是否至少为 $1$，故合法性判定是充要的。

按照两个字段合法性的四种组合处理输出，恰好符合题意。输出数值时自然去除了前导零。

复杂度分析

设输入行长为 $L$，时间复杂度为 $O(L)$，存储输入及字段所需的空间复杂度为 $O(L)$。

D. 双向取卡

出题人：苟立军

核心观察

记

$$q=\min(k-1,n-k+1).$$

将原序列两端的元素配成 $q$ 对，第 $i$ 对为 $(a_i,a_{n-i+1})$，其中 $1\le i\le q$。

每一对最终恰好取走一个元素，而且每对取走哪一个都可以自由选择。

若 $2(k-1)\le n$，原位置 $k$ 至 $n-k+1$ 的中间元素会全部被取走；否则，两端配对以外的中间元素都无法被取走。

因此，答案为

$$\mathrm{ans}=\sum_{i=1}^{q}\max(a_i,a_{n-i+1})+ \begin{cases} \displaystyle\sum_{i=k}^{n-k+1}a_i, & 2(k-1)\le n,\\ 0, & 2(k-1)>n. \end{cases}$$

其中，下限大于上限时，区间和视为 $0$。

正确性证明

先考虑 $n\ge 2k-1$。

在中间区间未清空前，两端各 $k-1$ 个元素受到位置保护，无法被取走，合法操作只会从中间区间的两端取走元素。因此，中间元素全部被取走，并留下长度为 $2k-2$ 的两端序列。

此时，若还有未处理的最内侧一对，其左右元素正好分别处在当前从右数第 $k$ 个和从左数第 $k$ 个位置。取走其中一个后，另一个进入中间保护区域，两个可取位置随之移向下一对。

已保留的元素位于两个可取位置之间，以后不会再被取走。归纳可知，各对由内到外处理，每对恰好取走一个，且选择互不限制。

若初始 $n<2k-1$，令 $q=n-k+1$。初始最内侧一对位于原位置 $q$ 与 $k$，恰好就是两个可取位置。中间的 $2k-n-2$ 个元素处在两个可取位置之间，始终受到保护。

沿用上述归纳，每次在当前最内侧的一对中任选一个取走，剩下一个受到保护，然后处理下一对，直到全部 $q$ 对处理完。此时恰好剩余 $k-1$ 个元素。

因此，对每一对选择较大值都能实际实现，且任何方案在该对的收益都不能超过它。加上必须取走的中间元素（若有），即得到最优答案。

当 $k=1$ 时，没有配对，全部元素都被取走，同样满足公式。

算法与复杂度

累加前 $q$ 对的较大值。若 $2(k-1)\le n$，再累加下标 $k$ 至 $n-k+1$ 的中间元素。

时间复杂度为 $O(n)$，使用数组的空间复杂度为 $O(n)$。答案可能达到 $10^{14}$，实现时应使用 64 位整数。

E. GTA 6 联机网络重组

出题人：邓文韬

算法思路

一次操作只能增加或删除一条边，代价都是 $1$。题目要求让 $A$ 与 $B$ 的连通块划分相同，无须让两者的边集相同。

图 $A$ 中，端点分别位于图 $B$ 的不同连通块的边，在最终图中不可能存在，必须全部删除。

删掉这些边以后，$A$ 的每个连通块都整体落在某个 $B$ 连通块内部。若某个 $B$ 连通块内还有 $p$ 个互不相连的 $A$ 碎片，补 $p-1$ 条边就能把它们连接成一个整体。

具体步骤如下：

1. 对 $B$ 建立并查集，得到每个顶点所属的连通块，记连通块数为 $k_B$。
2. 扫描 $A$ 的每条边。如果两个端点在 $B$ 中属于不同连通块，计入必须删除的边数 $D$；否则，将两个端点并入第二个并查集。
3. 统计第二个并查集的连通块数 $P$，孤立点也各算一个连通块。
4. 输出 $D+P-k_B$。

这里有

$$P-k_B=\sum_{C}(p_C-1),$$

其中，$C$ 遍历 $B$ 的所有连通块，$p_C$ 是 $C$ 内 $A$ 的碎片个数。

正确性证明

最终图中任意两点连通，当且仅当它们在 $B$ 中连通。

若 $A$ 中存在边 $(u,v)$，而 $u,v$ 在 $B$ 中不连通，则这条边在最终图中必须不存在，只能通过删除操作去掉。不同跨块边互不相同，因此删除次数至少为 $D$。

删掉跨块边后，设第 $i$ 个 $B$ 连通块内 $A$ 的碎片数为 $p_i$，有

$$\sum_{i=1}^{k_B}p_i=P.$$

最终第 $i$ 个 $B$ 连通块必须连通，而一次加边最多把两个碎片合并，所以至少需要 $p_i-1$ 次加边，合计不少于

$$\sum_{i=1}^{k_B}(p_i-1)=P-k_B.$$

这个下界可以取到：先删除全部 $D$ 条跨块边。此时，同一 $B$ 连通块内的两个不同碎片之间没有 $A$ 的边，任取两个碎片中的顶点 $x,y$，它们不相邻，添加边 $(x,y)$ 是合法的。

每添加一条这样的边，碎片数减少 $1$。添加 $p_i-1$ 条边后，该块内的所有顶点连通。对所有 $B$ 连通块重复此过程，总操作数恰为

$$D+P-k_B.$$

因此，算法得到的就是最少操作次数。

复杂度分析

使用两个并查集，时间复杂度为

$$O\bigl((n+m_1+m_2)\alpha(n)\bigr),$$

其中，$\alpha(n)$ 为反阿克曼函数。统计 $P$ 与 $k_B$ 各需 $O(n)$ 时间。

按存储顶点及边的实现，空间复杂度为 $O(n+m_1+m_2)$。实现时可使用 64 位整数保存答案。

F. GTA 6 最优信号匹配

出题人：邓文韬

算法思路

设当前已经确定要保留的二进制位组成掩码 $m$。最终答案包含这些位，当且仅当存在一种配对，使每一对设备在这些位上都不同，即

$$(a_i\mathbin{\&}m)=((\sim b'_i)\mathbin{\&}m).$$

因此，可以按照已选位上的模式分组：每组包含模式相同的 A 组元素，以及模式与其互补的 B 组元素。各组两侧的元素个数相同，组内可以任意配对，组间不能配对。

最初没有选定位，所有元素属于同一组。

从第 $29$ 位到第 $0$ 位依次尝试加入答案。在每个现有组内，记 A 组当前位为 $0$ 的元素个数为 $x$，B 组当前位为 $1$ 的元素个数为 $y$。

只有每组都满足 $x=y$，才能让所有配对在当前位上不同。由于两侧总数相等，A 组当前位为 $1$ 的数量也必然等于 B 组当前位为 $0$ 的数量。

若所有组均满足条件，就将当前位加入答案，并将每组分成两组：

• A 的 $0$ 与 B 的 $1$ 对应。
• A 的 $1$ 与 B 的 $0$ 对应。

忽略空组。否则不选择该位，保持原来的分组。

实现时，用两个数组和一组区间表示各组。先检查所有组，检查成功后，再分别按互补的位值原地划分两个数组。

数组内部的调整只是用于维护分组，不改变原问题中固定 A 组位置的要求，每个元素仍可对应回其原位置。题目只要求输出最大值，无须构造排列。

正确性证明

引理 1： 在选定位掩码为 $m$ 时，一种配对满足所有选定位，当且仅当每对元素位于同一个对应组内。

证明：满足这些位的要求，等价于 A 元素在 $m$ 上的模式与 B 元素在 $m$ 上的模式互补，这正是分组依据。因此，组内任意配对都满足要求，跨组配对则至少违反一个已选位。证毕。

引理 2： 在当前分组可行的前提下，能够额外选中第 $k$ 位，当且仅当每组中 A 的该位为 $0$ 的数量等于 B 的该位为 $1$ 的数量。

证明：由引理 1，只需考虑各组内部。若要求每对异或结果的当前位也为 $1$，A 的 $0$ 必须与 B 的 $1$ 配对，因此数量相等是必要条件。

该条件成立时，由两侧总数相等可知，A 的 $1$ 与 B 的 $0$ 的数量也相等，分别任意配对即可，所以该条件也是充分条件。划分得到的非空子组仍满足引理 1 的分组不变式。证毕。

定理： 算法输出的信号强度最大。

证明：从高位到低位进行归纳，初始时空掩码可行。

处理某一位时，若引理 2 的条件成立，就存在保持已选高位且选中当前位的方案。选中当前位的收益大于所有更低位的收益之和，因此最优答案应当选中该位。

若条件不成立，任何保留已选高位的方案都不能选中该位，只能跳过。

算法始终保留可行的最大前缀，处理完所有 $30$ 位后，即得到最大答案。证毕。

复杂度分析

每一位的检查与划分都会使每个元素被访问常数次，各组互不重叠。

每组测试数据的时间复杂度为 $O(30n)$，额外空间复杂度为 $O(n)$。所有测试数据的总时间复杂度为

$$O\left(30\sum n\right).$$