代码源挑战赛 Round 58 题解 - 代码源竞赛平台

T1

100%

根据题意，apiadu 第一天会阅读 $A$ 页。我们需要分情况讨论：

1. 如果小说的总页数 $X = A$，那么第一天就能读完，答案为 $1$。
2. 如果 $X > A$，第一天读完后还会剩余 $X - A$ 页。从第二天起，每天阅读 $B$ 页。剩余部分需要的天数可以通过向上取整得出，即 $\lceil \frac{X - A}{B} \rceil$。在整数除法中，向上取整可以使用公式 $(X - A + B - 1) / B$。

故最终总天数为 $1 + \lfloor \frac{X - A + B - 1}{B} \rfloor$。

T2

100%

由于只能按时间顺序从 $1$ 到 $n$ 秒进行遍历，我们用一个变量 $now$ 记录还需要多少秒相机才能正常运行。一开始 $now = 0$。

对于第 $i$ 秒，检查以下两个条件是否同时满足：

1. $now = 0$。
2. $a_i \ge P$ 如果同时满足，说明可以在此秒按下快门。照片总数加一，随后相机进入长达 $X$ 秒的冷却期，即 $now = X + 1$。

如果不满足上述任一条件，则跳过第 $i$ 秒继续扫描（记得更新 $now$ 的值，即$now = \max(0, now - 1)$）。

扫描完所有 $n$ 秒后统计出的照片数即为最优解。

时间复杂度 $O(n)$。

T3

100%

考虑交换排列中位于 $a_i$ 和 $b_i$（假设 $a_i < b_i$）的两个元素 $P_{a_i}$ 与 $P_{b_i}$。

根据逆序对的奇偶性变化规律（即每次对换操作必然改变排列逆序对数量的奇偶性），逆序对数量要么严格增加，要么严格减少，绝对不可能保持不变。

那么逆序对具体会怎么变化？我们可以证明：交换前如果 $P_{a_i} > P_{b_i}$，那么逆序对就会减少。交换前如果 $P_{a_i} < P_{b_i}$，那么逆序对就会增加。

我们考虑证明“交换前如果 $P_{a_i} > P_{b_i}$，那么逆序对就会减少”，后一段的证明方式是类似的。

具体证明如下：

设 $l<r$，$x=P_l$，$y=P_r$。

交换 $P_l$ 和 $P_r$ 后，只有涉及区间 $[l,r]$ 的逆序对可能变化。

若 $x>y$，则：

• $(l,r)$ 这一对逆序对消失；
• 对于 $l<k<r$，只有满足 $y<P_k<x$ 的元素会使逆序对数额外减少 $2$。

因此逆序对变化量为：$-1-2\cdot |\{k\mid l<k<r,\ y<P_k<x\}|$

一定小于 $0$。

若 $x<y$，同理，逆序对变化量为：$1+2\cdot |\{k\mid l<k<r,\ x<P_k<y\}|$

一定大于 $0$。所以交换会减少逆序对，当且仅当$P_l>P_r$

因此，“如果交换后 $P$ 的逆序对个数减少，则本轮交换”这一规则等价于：仅当 $P_{a_i} > P_{b_i}$ 时进行交换。直接模拟即可。

时间复杂度 $O(n + m)$。

T4

100%

设 $s_i$ 是满足周长是 $a_i$ 的三角形个数，由于数字对 $3$ 同余后均相同，我们可以考虑一下如果 $s_i$ 相同时 $a_i$ 满足什么条件。

可以发现当 $a_i + 3 = a_j$，$a_i$ 为奇数时，$s_i = s_j$。

• 两数相同，满足。
• 不相同。设对于任意的 $x$ 有 $x + 3 = a + b + c$（$a,b,c$ 为三角形的三边长度），则 $x = (a - 1) + (b - 1) + (c - 1)$。看起来对任意的周长为 $x$ 的三角形和周长为 $x + 3$ 的三角形的个数是相同的，但我们知道边长是大于 $0$ 的，所以当 $a = 1$ 或 $b = 1$ 或 $c = 1$ 时，上述 $x$ 是不构成三角形的。那么什么样的 $x$ 存在 $a,b,c = 1$ 呢？不妨设 $a = 1$，$b \ge c$，因为 $b - c < a$，所以 $b = c$，则 $x = 1 + 2b$，$x$ 为奇数。

于是 $x$ 和 $y$ 满足 $s(x)=s(y)$，当且仅当满足下面的条件：

1. $x=y$；
2. 或者 $|x-y|=3$，且较小的那个数是奇数。

只要记录每种数字的出现次数，用上面的方法统计即可。

T5

100%

解法 $1$

我们考虑按照 $1, n , 2 , n - 1 , 3 , n - 2 \cdots \frac{n}{2} ,\frac{n}{2} + 1$ 的顺序将它们恢复到原来的位置。

以 $1$ 为例，我们观察它是怎么回到原来的位置上的。

首先可以将 $1$ 移动到 $\frac{n}{2} + 1$ 的位置上，我们证明这是可行的。设 $1$ 在的位置是 $p$ ：

• $1 \leq p \leq \frac{n}{2}$：此时我们可以执行 $p - 1$次 l，然后执行 $\frac{n}{2} - (p - 1)$ 次 r，再执行一次 l，这样就能做到将 $1$ 放到 $\frac{n}{2} + 1$ 的位置上。
• $\frac{n}{2} < p \leq n$：此时我们可以先执行 $\frac{n}{2} - (p - 1 - \frac{n}{2})$ 次 l ，然后执行 $p - 1 - \frac{n}{2}$ 次 r，再执行一次 r，这样就能做到将 $1$ 放到 $\frac{n}{2} + 1$ 的位置上。
• 剩下的步骤l和 r 按照先 l 后 r 的顺序来填。（其实不必要）

将 $1$ 放到 $\frac{n}{2} + 1$ 的位置上之后，我们直接执行一次 r 就能将其复原到第一个位置上了。

接着我们以 $n$ 为例，观察它是怎么回到原来的位置上的。

注意：这里和移动 $1$ 有一些不同，因为我们要保证 $1$ 的位置不能改变。

与上面的做法类似，我们先考虑将 $n$ 移动到 $\frac{n}{2}$ 的位置上，再将其移动到第 $n$ 个位置。设 $1$ 在的位置是 $p$：

• $1 \leq p \leq \frac{n}{2}$：此时我们可以执行 $p - 1$次 l，然后执行 $(\frac{n}{2} - 1) - (p - 1)$ 次 r，再执行一次 l，这样就能做到将 $n$ 放到 $\frac{n}{2}$ 的位置上。
• $\frac{n}{2} < p < n$：此时我们可以执行 $(\frac{n}{2} - 1) - (p - 1 - \frac{n}{2})$ 次 l ，然后执行 $(p - 1) - \frac{n}{2}$ 次 r，再执行一次 r，这样就能做到将 $n$ 放到 $\frac{n}{2}$ 的位置上。
• $p = n$：这个时候已经在原来的位置上了，直接跳过整个步骤。
• 剩下的步骤l和 r 按照先 l 后 r 的顺序来填。（其实不必要）

将 $n$ 放到 $\frac{n}{2}$ 的位置上之后，第二次我们只要让最后一次是l，就能将其复原到第一个位置上了。

值得注意的是为什么 $p = n$ 要特判，因为如果将其并入到 $\frac{n}{2} < p < n$ 的情况内，那么执行 l 的次数将是$(\frac{n}{2} - 1) - (n - 1 - \frac{n}{2}) = 0$，那么这个时候 $1$ 就不会保持在原先的位置上了。

这样我们就把问题缩小成了长度为 $n - 2$ 的子问题，继续按照上述方法做即可。

时间复杂度 $O(n^2)$。

解法 $2$

本题存在在 $O(\log n)$ 次数内将其排序完成的做法。主要思想为 LSD 基数排序。

倒着思考：我们可以通过一个一开始升序的排列，一步一步变成题目给出的排列。

考虑倒着做操作具体的行为：给定一个由 $\frac{n}{2}$ 个 l 和 r 构成的字符串，按照这个规则做一次稳定划分（即 l 的数字在左侧，r 的数字在右侧，同样是 l或 r 就按照原先的顺序排序。）

例如：$a = [1,4,2,3]$，操作字符串为 lrrl，那么正着做（按照题目的要求）会得到 $a' = [1,2,3,4]$。那么如果我们按照上面的规则通过 lrrl 对 $a'$ 做操作，则会变成 $a$。

如果我们把 l 看成 $0$，r 看成 $1$，那么这里实际上就是做了一次稳定排序。

也就是说，如果每个数 $x$ 都有一个二进制标签 $tag_x$，那么每次倒着操作可以看成：

取出当前要排序的一位，把这一位为 $0$ 的元素稳定放到前面，把这一位为 $1$ 的元素稳定放到后面。

这正是 LSD 基数排序的过程。

如果我们从低位到高位依次做稳定划分，最终数组会按照这些二进制标签的字典序排序。

因此问题转化为：给每个数 $x$ 构造一个二进制标签 $tag_x$，使得按照标签排序后得到题目给出的排列 $a$，并且每一位上 $0$ 和 $1$ 的数量都恰好是 $\frac{n}{2}$？

设：$m=\frac{n}{2}$，令 $d=\lceil \log_2 m\rceil$

我们先构造 $m$ 个长度为 $d$ 的二进制串：

$$p_i = i \text{ 的 } d \text{ 位二进制表示}$$

然后构造 $n$ 个标签：

• 前 $m$ 个标签为：$0+p_0,\ 0+p_1,\ \dots,\ 0+p_{m-1}$

• 后 $m$ 个标签为：$1+\overline{p_{m-1}},\ 1+\overline{p_{m-2}},\ \dots,\ 1+\overline{p_0}$

其中 $\overline{p_i}$ 表示把 $p_i$ 中的每一位取反。

这组标签满足两个性质：

1. 标签是严格递增的；
2. 每一位上 $0$ 的数量和 $1$ 的数量都恰好为 $m$。

第一个性质比较直观。前半部分最高位为 $0$，后半部分最高位为 $1$，因此前半部分一定小于后半部分。前半部分内部按 $p_i$ 递增。后半部分因为 $p_i$ 是倒序枚举后再取反，所以也递增。

第二个性质也容易证明。最高位显然有 $m$ 个 $0$ 和 $m$ 个 $1$。对于后面的任意一位，假设前半部分这一位有 $c$ 个 $0$，则有 $m-c$ 个 $1$。后半部分是取反得到的，所以这一位有 $m-c$ 个 $0$，有 $c$ 个 $1$。故：

• $1$ 的个数为 $(m - c) + c = m$
• $0$ 的个数为 $c + (m - c) = m$

故满足性质 $2$。故这就是我们满足条件的标签。

接下来，把这些标签依次分配给排列 $a$ 中的元素。

也就是说，若上面构造出的第 $i$ 个标签为 $row_i$，则令：$tag_{a_i}=row_i$

这样按照 $tag$ 从小到大排序时，得到的顺序正好是：$a_1,a_2,\dots,a_n$

接下来倒着模拟 LSD 基数排序即可。

令：$cur=[1,2,\dots,n]$

然后从标签的最低位到最高位依次处理。对于当前数组 $cur$，构造一个操作字符串 $s$：

• 如果当前元素这一位为 $0$，则 $s$ 的对应位置填 l；
• 如果当前元素这一位为 $1$，则 $s$ 的对应位置填 r。

然后把 $cur$ 按照这一位稳定划分：

$$cur = \text{所有这一位为 }0\text{ 的元素} + \text{所有这一位为 }1\text{ 的元素}$$

经过所有位之后，$cur$ 会按照标签字典序排列，也就是变成原排列 $a$。

但是这是倒着构造出来的过程。真正要把 $a$ 排成升序，只需要把记录下来的操作字符串倒序输出即可。

时间复杂度为 $O(n\log n)$。

T6

100%

首先我们可以证明大于 $1$ 的奇数无解。

设城市 $i$ 选择的边为：$i \to 2i + b_i \pmod n$，其中 $b_i=0$ 表示选择 A，$b_i=1$ 表示选择 B。

如果存在哈密顿回路，那么所有目标点也必须恰好是 $0\sim n-1$ 的一个排列。

设 $B=\sum b_i$，即选择 B 门的数量。

因为目标点是一个排列，所以模 $n$ 意义下有：

$$\sum_{i=0}^{n-1} i \equiv \sum_{i=0}^{n-1}(2i+b_i)\pmod n$$

即：

$$S \equiv 2S + B \pmod n$$

所以：

$$B \equiv -S \pmod n$$

其中：

$S=\frac{n(n-1)}2$

当 $n$ 为奇数时，$\frac{n-1}{2}$ 是整数，因此：

$$S \equiv 0 \pmod n$$

于是：

$$B \equiv 0 \pmod n$$

又因为 $0\le B\le n$，所以只有两种可能：

• $B=0$：所有点都选 A，此时 $0\to 0$，存在自环；
• $B=n$：所有点都选 B，此时 $n-1\to n-1$，存在自环。

当 $n>1$ 时，这两种情况都不可能形成长度为 $n$ 的环。

因此，大于 $1$ 的奇数无解。

现在我们考虑偶数的构造方法。

解法 $1$

令 $m = \frac{n}{2}$，对于 $0 \leq i < m$ 的编号，可以观察到：

• $i$ 的 A 门编号为 $2i \bmod n$， $i + m$ 的 A 门编号为 $(2(i + m)) \bmod n = 2i \bmod n$，也就是说 $i$ 的 A 门编号与 $i + m$ 的 $A$ 门编号相同。

• $i$ 的 B 门编号为 $(2i + 1) \bmod n$， $i + m$ 的 B 门编号为 $(2(i + m) + 1 ) \bmod n = (2i + 1) \bmod n$，也就是说 $i$ 的 B 门编号与 $i + m$ 的 B 门编号相同。

因此，对每一对 $(i,i+m)$，只要一个选 A，一个选 B，那么目标点 $2i$ 和 $2i+1$ 就都会恰好被进入一次。

那么只要：$i$ 选 A，$i+m$ 选 B，这个时候已经构造出一个排列 $P_i$ 了，但是对应的图不一定是一个环。

初始构造后，可能有多个环。接下来枚举每一对 $(i,i+m)$。

如果 $i$ 和 $i + m$ 不在同一个环内，那么就交换他们对应的传送门。

这样仍然保证 $2i$ 和 $2i+1$ 各有一个入边，因此图仍然是一个排列。同时，由于 $i$ 和 $i+m$ 原本在两个不同的环中，交换它们的出边会把这两个环拼成一个更大的环。

对每个 $i$（$0 \leq i < m$）的点都做一次上面的操作，这样就可以构成一整个环。

时间复杂度 $O(n)$。

解法 $2$

同样令 $m = \frac{n}{2}$。

考虑构造一个新图 $G_m$，它有 $m$ 个点，编号为 $0\sim m-1$。

对于每个点 $u$，连两条有向边：

• A 边 ：$u\to 2u\bmod m$
• B 边： $u\to (2u+1)\bmod m$

这个图一共有 $2m=n$ 条边。

我们把 $G_m$ 中的一条边对应到原图 $G_n$ 中的一个城市。

具体地，边 $u \xrightarrow{b} (2u+b)\bmod m$ 对应原图中的城市 $2u+b$，其中 $b=0$ 表示 A 边，$b=1$ 表示 B 边。

因为 $0\le u<m$，所以 $2u+b$ 恰好可以表示 $0\sim n-1$ 的所有城市。

对着这个新图做一次欧拉回路。不难证明欧拉回路存在。

假设欧拉回路的边序列对应的城市编号为：

$$e_0,e_1,\dots,e_{n-1}$$

其中每个 $e_i$ 是 $0\sim n-1$ 的一个城市编号。

对于城市 $e_i$，它下一步要走到 $e_{i+1}$。

• 如果 $e_{i+1}$ 是偶数，则 $s_{e_i}=\texttt{A}$；
• 如果 $e_{i+1}$ 是奇数，则 $s_{e_i}=\texttt{B}$。

注意最后一个城市 $e_{n-1}$ 的下一步是 $e_0$。

时间复杂度 $O(n)$。

构造的证明如下：

设欧拉回路中连续两条边为：

$$u\xrightarrow{b}v,\qquad v\xrightarrow{c}w$$

第一条边对应原图城市：

$$x=2u+b$$

第二条边对应原图城市：

$$y=2v+c$$

因为：

$$v\equiv x\pmod m$$

所以：

$$y=2v+c\equiv 2x+c\pmod {2m}$$

也就是：

$$y\equiv 2x+c\pmod n$$

因此若下一条边对应的城市 $y$ 是偶数，即 $c=0$，城市 $x$ 选 A；若 $y$ 是奇数，即 $c=1$，城市 $x$ 选 B。

这样欧拉回路经过每条边一次，正好对应原图中每个城市访问一次。