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

T1

$100\%$

读入$hh$ 和 $mm$ 后，让 $mm$加上 $15 - (mm \% 15)$，再处理进位的情况即可。

输出的时候可以用 printf("%02d:%02d\n", hh, mm); 来处理前导 $0$。

T2

$100\%$

当 $k$ 高达 $100$ 时，需要使用字符串处理高精度运算。由于被减数的每一位都是 $9$，这意味着减法过程中不会发生借位。所以处理出对应的值即可。注意前导 $0$ 和 $x = 10^k -1$ 这两种情况即可。

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

T3

$100\%$

灯 $i$ 的最终状态只取决于它总共被拨动了多少次。利用差分数组算出每个灯对应的操作次数，然后对 $h_i$ 取模即可。

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

T4

$100\%$

问题等价于：找到地图上所有的连通块，计算每个连通块的周长，并将周长赋值给块内的所有点。

找连通块这个过程我们可以用 BFS 算出每一个连通块的形状。对于每个连通块，可以计算出每个位置周围不是联通块的边界数，把他们加起来就得到了整个连通块的周长，算出周长后对每个连通块内的值赋值即可。

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

T5

100%

题目要求我们在 $K$ 个重复的序列 $a$ 拼接而成的长序列 $X$ 中，找到满足 $X_p > X_q > X_r$ 且 $p < q < r$ 的三元组数量。

我们可以 $O(n^2)$ 或者 $O(n \log n)$ 预处理出下面数组的值：

• $L1[i]$：在 $i$ 左边且比 $a_i$大的数的个数。
• $R1[i]$：在 $i$ 右边且比 $a_i$大的数的个数。
• $L2[i]$：在 $i$ 左边且比 $a_i$小的数的个数。
• $R2[i]$：在 $i$ 右边且比 $a_i$小的数的个数。

与其去思考三个数分别在哪里，不如固定中间那个数 $X_q$。

假设中间的数 $X_q$ 对应原序列 $a$ 中的下标为 $i$（数值为 $a_i$）。由于序列重复了 $K$ 次，这个 $a_i$ 可能出现在第 $1$ 到第 $K$ 个块中的任意一个。

我们需要确定三元组 $(X_p, X_q, X_r)$ 的分布情况。根据 $p, q, r$ 所在的“块”不同，可以分为 4 种情况。

由于序列重复了 $K$ 次，对于一个固定的中间值 $a_i$（位于第 $mid$ 块），其左边的大数可以来自同一个块，也可以来自前面的块；右边的小数同理。

根据三元组 $(p, q, r)$ 分别所在的“块”及其相对位置，可以分为以下 4 种情况计算贡献：

• 情况 1：三个数跨越了 3 个不同的块

  • 我们要从 $K$ 个块中选 3 个，方案数为 $\binom{K}{3}$。
  • 左边的数在更早的块，只要比 $a_i$ 大即可。
  • 右边的数在更晚的块，只要比 $a_i$ 小即可。
  • 贡献：$(L1[i] + R1[i]) \times (L2[i] + R2[i]) \times \binom{K}{3}$。

• 情况 2：前两个数在同一个块，第三个数在后面的块

  • 我们要从 $K$ 个块中选 2 个，方案数为 $\binom{K}{2}$。
  • 左边的数必须在当前块且在 $a_i$ 左侧。
  • 右边的数在更晚的块。
  • 贡献：$L1[i] \times (L2[i] + R2[i]) \times \binom{K}{2}$。

• 情况 3：第一个数在前面的块，后两个数在同一个块

  • 同样选 2 个块，方案数为 $\binom{K}{2}$。
  • 左边的数在更早的块。
  • 右边的数必须在当前块且在 $a_i$ 右侧 。
  • 贡献：$(L1[i] + R1[i]) \times R2[i] \times \binom{K}{2}$。

• 情况 4：三个数都在同一个块

  • 从 $K$ 个块中选 1 个，方案数为 $\binom{K}{1} = K$。
  • 左边的数在当前块左侧，右边的数在当前块右侧。
  • 贡献：$L1[i] \times R2[i] \times K$。

将以上四部分累加并对 $998244353$ 取模即可。

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

T6

$100\%$

我们需要计算的表达式是：

$$\sum_{s \in S} \text{popcount}(s \oplus (s + x))$$

考虑二进制加法 $s + x$。令 $c_k$ 表示在第 $k$ 位上的进位（$c_0 = 0$）。

此时第 $k$ 位的和是 $s_k \oplus x_k \oplus c_k$。

那么，$s \oplus (s + x)$ 在第 $k$ 位的值为：

$$s_k \oplus (s_k \oplus x_k \oplus c_k) = x_k \oplus c_k$$

这意味着，$\text{popcount}(s \oplus (s + x))$ 等于：

$$\sum_{k=0}^{29} (x_k \oplus c_k)$$

其中 $x_k$ 是 $x$ 的第 $k$ 位，$c_k$ 是 $s+x$ 运算中进入第 $k$ 位的进位。

考虑进位 $c_k$ 是如何产生的。

$c_k = 1$ 当且仅当 $s$ 的低 $k$ 位加上 $x$ 的低 $k$ 位产生了溢出（即大于等于 $2^k$）。

数学上表示为：

$$c_k = 1 \iff (s \bmod 2^k) + (x \bmod 2^k) \ge 2^k \iff x \bmod 2^k \ge 2^k - (s \bmod 2^k)$$

于是问题就变成了：

对于每一个二进制位 $k$（从 $0$ 到 $29$），统计集合 $S$ 中有多少个元素 $s$，满足 $s \bmod 2^k \ge T_k$，其中 $T_k = 2^k - (x \bmod 2^k)$。记这个数量为 $cnt_k$。

• 根据公式 $x_k \oplus c_k$：
  • 如果 $x$ 的第 $k$ 位是 $0$ ($x_k=0$)：我们需要加上 $c_k=1$ 的数量。即贡献为 $cnt_k$。
  • 如果 $x$ 的第 $k$ 位是 $1$ ($x_k=1$)：我们需要加上 $c_k=0$ 的数量。即贡献为 $|S| - cnt_k$。

这个 $cnt_k$ 可以用树状数组或其他数据结构来维护即可。（即添加 $x \bmod 2^k$ ，查询 $\ge 2^k - (s \bmod 2^k)$ 的结果。）

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