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

T1

100%

题目规定“买 $3$ 瓶送 $1$ 瓶”，这意味着每获得 $4$ 瓶可乐，只需要支付 $3$ 瓶的钱（即 $3x$ 元）。我们将需要购买的 $n$ 瓶可乐分成两部分：

能凑成“买 $3$ 送 $1$ ”整捆的部分：一共有 $\lfloor \frac{n}{4} \rfloor$ 捆，每一捆需要花费 $3x$ 元。
剩下的零头部分：有 $n \bmod 4$ 瓶，这些只能以单价 $x$ 元购买。

最小花费 $= \lfloor \frac{n}{4} \rfloor \times 3x + (n \bmod 4) \times x$

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

T2

100%

按照题意，对于输入字符串 $s$ 中的每一个字符，我们都需要将其重复输出 $k$ 次。只需从左到右遍历字符串的每一个字符，内层使用一个循环将当前字符连续输出 $k$ 次即可。

时间复杂度： $O(n \times k)$ 。

T3

100%

可以发现，在“从右上往左下”的对角线上，所有元素的行列坐标 $(i, j)$ 之和 $i + j$ 都是相等的。所以我们按照 $i + j$ 的值进行排序，如果 $i + j$ 的值相同，则按照 $i$ 从小到大排序，这样我们就得到了一个坐标序列，其中第 $i$ 个坐标就是要填数字 $i$ 的位置。模拟即可。

时间复杂度： $O(n^2 \log(n^2))$ ，即 $O(n^2 \log n)$ 。

当然本题也可以直接枚举每条对角线的起始位置后一步一步填数，这里不再赘述。时间复杂度为 $O(n^2)$ 。

T4

100%

题目允许“最多换乘一次”。这意味着从点 $1$ 到点 $n$ 的合法路径只能是以下四种形式之一：

全程只乘坐 A 类轨道。
全程只乘坐 B 类轨道。
从点 $1$ 出发乘坐 A 类轨道到达某个中转城市 $u$ ，然后换乘 B 类轨道到达点 $n$ 。
从点 $1$ 出发乘坐 B 类轨道到达某个中转城市 $u$ ，然后换乘 A 类轨道到达点 $n$ 。

由于所有轨道长度为 $1$ ，我们可以分别在 A 轨道网络和 B 轨道网络中用 BFS 算出下面几个数组的值：

$distA_1[u]$ ：在 A 网络中，从点 $1$ 到点 $u$ 的最短距离。
$distB_1[u]$ ：在 B 网络中，从点 $1$ 到点 $u$ 的最短距离。
$distA_n[u]$ ：在 A 网络中，从点 $n$ 到点 $u$ 的最短距离。
$distB_n[u]$ ：在 B 网络中，从点 $n$ 到点 $u$ 的最短距离。

最终答案为以下各项中的最小值：

$distA_1[n]$
$distB_1[n]$
对于所有的中转点 $u \in [1, n]$ ： $distA_1[u] + distB_n[u]$
对于所有的中转点 $u \in [1, n]$ ： $distB_1[u] + distA_n[u]$

时间复杂度为 $O(n + m_1 + m_2)$ 。

T5

100%

我们需要快速求出字符串 $x$ 循环右移 $k$ 位后的数值 $f(k)$ 。由于右移是以 $n$ 为周期的，实际上只需要求出 $f(0), f(1), \dots, f(n-1)$ 。

设 $x$ 的初始数值为 $V_0$ ，其作为字符串的最后一位字符代表的数字为 $d$ 。当我们将 $x$ 循环右移一位时，实际上是把原数字的个位 $d$ 砍掉，将剩下的部分整体右移一位（相当于除以 $10$ ），然后再把 $d$ 放到最高位（加上 $d \times 10^{n-1}$ ）。

利用上面的方法，我们可以用递推预处理出所有可能的右移次数 $k \in [0, n-1]$ 的结果 $f(k)$ 。对于序列 $l$ ，我们统计每个位移量 $l_i \bmod n$ 出现的次数，最后直接将对应的 $f(l_i \mod n)$ 乘上频次并累加求和即可。

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

T6

100%

题目要求寻找最小的正整数 $x$ ，使得 $x(x+1)$ 是 $a$ 的倍数，即 $a \mid x(x+1)$ 。

由于连续两个整数 $x$ 和 $x+1$ 必然互质（ $\gcd(x, x+1) = 1$ ），我们可以将 $a$ 分解为两个互质的因数 $u$ 和 $v$ （满足 $a = u \times v$ 且 $\gcd(u, v) = 1$ ），使得：

$u \mid x$ （即 $x \equiv 0 \pmod u$ ）
$v \mid x+1$ （即 $x + 1\equiv 0 \pmod v$ ）

令 $x = X u$ ，带入 $x \equiv -1 \pmod v$ ，有 $Xu + 1\equiv 0 \pmod v$ 。令 $Yv = Xu + 1$ ，可以发现这是一个不定方程。利用 exgcd 算出最小的正数 $X$ ，此时答案为 $X u$ ，取最小值即可。

时间复杂度为 $O(T \sqrt{N} \log N)$ 。