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

T1

100%

读入整数 $n$，计算其个位数字 $d = n \bmod 10$。

• 如果 $0 \le d \le 4$，输出 $n - d$。
• 如果 $5 \le d \le 9$，输出 $n - d + 10$。

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

T2

100%

由于数据范围 $n \le 1000$，我们可以直接使用两重循环枚举所有的 $(i, j)$。

第一层循环枚举 $i$ 从 $1$ 到 $n$，第二层循环枚举 $j$ 从 $1$ 到 $n$。 如果满足 $a_i = b_j$ 且 $i \neq j$，则计数器加一。

最后输出计数器的值。

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

T3

100%

本题实质上是矩阵乘法。

根据题目定义：

• 生产 $1$ 个产品 $i$ 需要 $a_{i,k}$ 个零件 $k$。
• 生产 $1$ 个零件 $k$ 需要 $b_{k,j}$ 个原料 $j$。

则生产 $1$ 个产品 $i$ 所需的原料 $j$ 的总数为：所有可能的零件 $k$ 消耗的原料的和。 即：$c_{i,j} = \sum_{k=1}^{n} a_{i,k} \times b_{k,j}$。

直接使用三重循环计算即可。

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

T4

100%

本题要求通过交换相邻元素将序列 $1, 2, \dots, n$ 变换为目标排列 $a$。这等价于对目标排列 $a$ 进行排序的逆过程，或者直接理解为将小球从初始位置路由到目标位置。

容易发现，这个问题等价于对排列 $a$ 进行排序，每次“安装轨道”的操作本质上就是交换相邻的两个球。我们可以利用冒泡排序的思想来解决这个问题。

对于第 $i$ 个位置，我们可以先找到 $a_i$ 这个小球所在的位置 $j$，然后通过交换把 $a_i$ 这个小球一步步交换到 $i$ 这个位置即可。每次交换时，记录此时交换的操作，由于高度决定了交换的先后顺序，只要保证 $h$ 降序即可。

冒泡排序的交换次数等于逆序对的数量，最坏情况下为 $\frac{n(n-1)}{2}$，满足题目 $k \le n^2$ 的限制。

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

T5

100%

首先观察答案的性质：如果我们能以体力 $H$ 采摘 $k$ 个果子，那么对于任意 $H' > H$，我们也一定能采摘 $k$ 个果子（可选范围变大了）。答案具有单调性。

因此可以二分答案 $H$。

对于固定的最大高度 $H$，问题转化为：在树上只考虑深度 $\le H$ 的节点，选出最多权值的果子，且满足“若选了变异点，则不能选其邻居”的约束。

这是一个树上最大权独立集问题的变体。 由于冲突关系仅存在于（变异点，邻居）之间，这依然是一个树上的动态规划问题。这状态为：

• $dp[u][0]$：不选点 $u$，以 $u$ 为根的子树能选的最大果子数。
• $dp[u][1]$：选点 $u$，以 $u$ 为根的子树能选的最大果子数。

转移方程：

• $dp[u][0] = \sum_{v \in son(u)} \max(dp[v][0], dp[v][1])$
• $dp[u][1] = a_u + \sum_{v \in son(u)} \text{val}(u, v)$ 其中，如果 $u$ 是变异点或者 $v$ 是变异点，则 $u, v$ 不能同时选，故 $\text{val}(u, v) = dp[v][0]$； 否则（$u, v$ 都不是变异点），没有限制，$\text{val}(u, v) = \max(dp[v][0], dp[v][1])$。

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

T6

100%

$k$ 高达 $10^{18}$，$n$ 只有 $50$。这提示我们使用矩阵快速幂。

每一秒的操作是一个线性变换。设第 $k$ 秒时各点的权值为列向量 $\mathbf{A}_k$。 $\mathbf{A}_{k+1} = \mathbf{T} \times \mathbf{A}_k$。 其中转移矩阵 $\mathbf{T}$ 的构造如下：

• $\mathbf{T}$ 是一个 $n \times n$ 的矩阵。
• 若点 $u$ 和点 $v$ 相连，则点 $u$ 会分给 $v$ 一部分权值，比例为 $1/deg[u]$。
• 对应矩阵元素 $T_{v, u} = \frac{1}{deg[u]}$（注意：第 $v$ 行 第 $u$ 列，表示 $u$ 贡献给 $v$）。
• 若 $u, v$ 不相连，则 $T_{v, u} = 0$。

计算 $\mathbf{T}^k \times \mathbf{A}_0$ 即可。

注意全程在模 $998244353$ 下运算，分数需要使用逆元。

时间复杂度 $O(n^3 \log k)$。

T7

100%

设集合 $S$ 中去重后的元素为 $v_1, v_2, \dots, v_d$，其在 $S$ 中出现的次数分别为 $c_1, c_2, \dots, c_d$。设 $\text{ Distinct}(S)$ 为 $S$ 去重后的集合，即 $\text{ Distinct}(S) = \{ v_1 ,v_2 ,\cdots ,v_d \}$。 记 $|S|$ 为集合 $S$ 的元素总数（即区间长度）。

我们需要求 $G(S) = \sum_{T \subseteq S} (\sum_{x \in T, x \text{ 在 } T\text{ 中出现奇数次 } }x)^2$。 展开平方项： $(\sum x)^2 = \sum x^2 + \sum_{x \neq y} xy$。

考虑 $S$ 中某一种数值 $u$ 对答案的贡献（$u^2$ 的系数）： 我们在 $S$ 中有 $c_u$ 个 $u$。在子集 $T$ 中，若 $u$ 出现了奇数次，则贡献 $u^2$。

• $u$ 出现奇数次的方案数：$\binom{c_u}{1} + \binom{c_u}{3} + \dots = 2^{c_u-1}$。
• 其他元素任意选的方案数：$2^{|S| - c_u}$。
• 总贡献次数：$2^{c_u-1} \times 2^{|S|- c_u} = 2^{|S| - 1}$。可以发现，系数与这个数的出现次数无关。 即：$2^{|S| - 1} \times \sum_{u \in \text{ Distinct} (S)} u^2$。

考虑 $\text{ Distinct}(S)$ 中两种不同数值 $u, v$ 对答案的贡献（$2uv$ 的系数）： 我们需要 $u$ 在 $T$ 中出现奇数次，且 $v$ 在 $T$ 中出现奇数次。

• $u$ 奇数次方案：$2^{c_u-1}$。
• $v$ 奇数次方案：$2^{c_v-1}$。
• 其他元素任意选：$2^{|S| - c_u - c_v}$。
• 总方案数：$2^{c_u-1} \cdot 2^{c_v-1} \cdot 2^{|S| - c_u - c_v} = 2^{|S| - 2}$。 即：$\sum_{u,v \in \text{Distinct}(S) \wedge u \neq v \wedge (u,v) 是 无序对} 2uv \times 2^{|S| - 2} = 2^{|S| - 2} \times\sum_{u,v \in \text{Distinct}(S)\wedge u \neq v \wedge (u,v) 是 有序对} uv$。

此时 $\sum_{u \neq v} uv$ 仍然不好维护，不过可以转换成便于维护的形式：

$$\sum_{u,v \in \text{Distinct}(S)\wedge u \neq v \wedge (u,v) 是 有序对} uv = (\sum_{u \in \text{Distinct}(S)} u)^2 - \sum_{u \in \text{Distinct}(S)} u^2$$

整理待计算的公式可得：

$$\begin{aligned} G(S) &= \sum_{T \subseteq S} (\sum_{x \in T, x \text{ 在 } T\text{ 中出现奇数次 } }x)^2\\ &=2^{|S| - 1} \sum_{u \in \text{Distinct}(S)} u^2 + \sum_{u,v \in \text{Distinct}(S)\wedge u \neq v \wedge (u,v) 是 无序对} 2uv \times 2^{|S| - 2} \\ &= 2^{|S| - 2} (2 \times \sum_{u \in \text{Distinct}(S)} u^2 + (\sum_{u \in \text{Distinct}(S)} u)^2 - \sum_{u \in \text{Distinct}(S)} u^2) \\ &= 2^{|S| - 2}(\sum_{u \in \text{Distinct}(S)} u^2 + (\sum_{u \in \text{Distinct}(S)} u)^2) \end{aligned}$$

现在的问题就变成了：给定若干次询问，每次询问给出一个区间 $[l,r]$，求区间中不同元素的值的和以及不同元素的平方和。

这是一个静态区间数颜色的变形（[SDOI2009] HH 的项链），利用离线+树状数组或线段树维护区间中不同元素的和以及平方和即可。时间复杂度为 $O((n + m) \log n)$。