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

T1

100%

我们知道 $365 \equiv 1 \pmod 7$。 这意味着每过一年，同一日期的星期数会向后推移 $1$ 天（例如从星期四变成星期五）。 反过来看，要保持“星期五”这个属性，日期就需要向前推移 $1$ 天（例如从 $2$ 号变成 $1$ 号）。 在模 $7$ 意义下，日期减 $1$ 等价于加 $6$。

因此，设 $n$ 年的第一个星期五的日期为 $d_n$，则有递推公式：

$$d_n \equiv (d_{2026} + (n - 2026) \times 6) \pmod 7$$

其中 $d_{2026} = 2$。

注意计算时负数的情况。

T2

100%

这是一道贪心模拟题。

我们需要维护一个变量 $now$ 表示当前积压的任务数量。初始为 $0$。 从第 $1$ 天遍历到第 $n$ 天：

1. 接任务：$now$ 加上当天下发的任务数 $a_i$。
2. 做任务：当天能处理的任务数是 $\min (now , x )$。
3. 更新 $now$：$now$ 减去 $\min(now ,x)$。

循环结束后，$now$ 即为第 $n$ 天结束时剩余的任务总量。

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

T3

40%

对于每次询问，暴力遍历区间 $[l, r]$，计算周长。 周长由以下几部分组成：

1. 底部长度：$r - l + 1$。
2. 顶部水平长度总和：$r - l + 1$（因为矩形宽度均为 1）。
3. 左右外侧边：$a_l$ 和 $a_r$。
4. 内部及顶部垂直边：相邻矩形的高度差绝对值之和，即 $\sum_{i=l + 1}^{r} |a_i - a_{i-1}|$。

总公式为：$2 \times (r - l + 1) + a_l + a_r + \sum_{i=l + 1}^{r} |a_i - a_{i-1}|$。

暴力计算的时间复杂度为 $O(n \cdot q)$。

100%

观察上述公式，瓶颈在于计算区间相邻项差值的绝对值之和 $\sum_{i=l + 1}^{r} |a_i - a_{i-1}|$。 这可以通过前缀和进行优化。

定义数组 $b$，其中 $b_i =|a_i - a_{i-1}|$ （对于 $2 \le i \leq n$）。

构造 $b$ 的前缀和数组 $S$，其中 $S_k = \sum_{j=1}^{k} b_j$。

那么 $\sum_{i=l + 1}^{r} |a_i - a_{i-1}|$ 就可以用 $S_{r} - S_{l}$ 在 $O(1)$ 时间内求出。

特别注意当 $l=r$ 时，求和部分为 $0$。

预处理时间 $O(n)$，查询时间 $O(1)$，总时间复杂度 $O(n + q)$。

T4

100%

设 $pre$ 是构造出来的数组的前缀异或和。

先考虑 $t_i = 0$，如果 $t_i = 0$，那么要获胜的条件就是 $pre_{l - 1} \text{ xor } pre_r = 0$。

为什么？

假设第一个人的分数是 $s_1$ ，第二个人的分数是 $s_2$，那么要获胜的条件就是 $s_1 = s_2$，也就是 $s_1 \text{ xor } s_2 = 0$。

同时 $s_1 \text{ xor } s_2$ 也是$a_l \text{ xor } a_{l + 1} \text{ xor } a_{l +2} \cdots a_r = pre_{l - 1} \text{ xor } pre_r$ 的值，故 $pre_{l - 1} \text{ xor } pre_r$ 也得是 $0$。

我们考虑一个 $n + 1$ 个节点的图（编号从 $0$ 到 $n$），如果 $t_i = 0$，那么就让 $l - 1$ 和 $r$ 之间连一条无向边，表示 $pre_{l - 1} = pre_{r}$。

这时我们考虑将这个图进行染色（染色的值就表示 $pre$ 的值），其中每个连通块染的颜色都相同。

这个时候再考虑剩下的条件，剩下 $t_i = 1$ 的限制我们可以尽量满足，也就是让图中的不同联通块的值都不一样，此时再检查所有 $t_i = 1$ 的限制，看看是否满足，不满足则输出 $-1$。

以及最后一个 $a_i \not = 0$ 的条件，等价于 i i+1 1，记得处理即可。

此时我们得到了前缀异或值，只要将其转换为原来的 $a$ 数组即可。

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

T5

100%

利用二进制分解的思想构造。

我们考虑构造出一些点 $v_0, v_1 ,v_2 ,\cdots, v_{29}$（$v_i \not= 1$ 且 $v_i \not= n$），其中 $v_i$ 到 $n$ 的路径数量为 $2^i$。如果我们构造出了这些点，接下来只要根据 $K$ 的二进制表示来进行连边，就能得到答案。（如果 $K$ 的第 $i$ 位是 $1$，就将 $1$ 向 $v_i$ 连一条边）

先考虑 $v_0$ 的构造，我们只需要将 $v_0$ 直接连向 $n$ 即可。

假设我们已经完成了 $v_0 , v_1 ,v_2, \cdots v_{i -1}$，如何构造出 $v_i$ 呢？

我们可以让 $v_i$ 分别向 $v_0 , v_1 ,v_2 ,\cdots v_{i -1}$ 连一条边，再向 $n$ 连一条边即可。

此时 $v_i$ 到 $n$ 的方案数为 $2^0 + 2^1 + 2^2 + \cdots 2^{i - 1} + 1 = 2^i$，满足条件。

T6

100%

首先，我们可以除去每个数 $a_i$ 中所有的平方因子，只保留“无平方因子部分”。 例如：$12 = 2^2 \times 3 \to 3$，$8 = 2^2 \times 2 \to 2$，$44 = 2^2 \times 11 \to 11$。

此时 $a_i$ 和 $a_j$ 如果满足条件，则变成了： $a_i = a_j \times p$, 或者 $v = u \times p$。其中 $p$ 是任意质数。

考虑莫队，同时维护出以下两个数组：

1. $cnt[x]$：表示数值 $x$ 在当前区间内出现的次数。
2. $f[y]$：辅助数组。由于我们要找的是 $x = y \times p$ 的关系，$f[y]$ 表示当前区间内有多少个大数 $Z$，满足 $Z$ 去掉一个质因子后等于 $y$（即 $Z$ 是 $y$ 的质数倍）。

现在考虑插入一个数 $x$ 时，对答案的贡献：

1. $x$ 作为大数时，我们考虑枚举其所有的质因子 $p$，其中 $(\frac{x}{p}, x)$ 的贡献为 $cnt[\frac{x}{p}]$。
2. $x$ 作为小数时，贡献为 $f[x]$。

最后记得更新 $f[\frac{x}{p}]$ 的值。

删除数的想法类似，这里不再赘述。

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