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

T1

100%

ay = c - b

y = \frac{c - b}{a}

题目要求输出不大于 $y$ 的最大整数 $y'$ 。由于题目保证了 $b \le c$ 且 $a \ge 1$ ，因此 $c - b \ge 0$ 。对于非负数，不大于它的最大整数就是它的向下取整值。因此直接输出 (c - b) / a 即可。

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

T2

100%

每件礼物的实际贡献（心意值）是其基础价值与惊喜度的乘积，即 $V_i \times P_i$ 。为了用最少数量的礼物达到或超过目标心意值 $X$ ，我们显然应该优先选择贡献最大的礼物。

故只需要将礼物按照心意值进行排序，之后一个一个取，直到对应的心意值 $> X$ （注意不是 $\ge X$ ）即可。

如果都取完了还没有满足条件，输出 -1。

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

T3

100%

根据题意，一个数字 $k$ 是“好的”，当且仅当它的所有质因数都完全包含在给定的质数序列 $a$ 中。由于题目保证了给定的序列 $a$ 中的元素全是质数，我们可以直接利用试除法来验证。

对于每一次询问的数字 $k$ ：

我们遍历给定的质数序列 $a$ 中的每一个元素 $a_i$ 。
如果当前的 $k$ 能够被 $a_i$ 整除，我们就通过不断除 $a_i$ 直到不能整除为止，通过这种方式将 $k$ 中的 $a_i$ 因子剥离出去。
当遍历完整个序列 $a$ 后，如果 $k$ 最后变成了 $1$ ，说明 $k$ 的所有质因数都在序列 $a$ 中，那么它就是一个“好的”数字，输出 YES；如果 $k > 1$ ，说明 $k$ 还含有序列 $a$ 之外的质因数，因此输出 NO。

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

T4

100%

这个题主要的难点在于如何维护一个支持“尾部追加”和“局部连续删除”且删除后能维持先后顺序的数据结构。我们可以利用 set 来完成这一模拟过程。

由于每次放置新牌时，都是将其放在桌面所有牌的最右侧，这意味着：牌在桌面上的相对左右顺序，与它们被抽出来的回合序号（即初始序号 $i$ ）的大小顺序是完全一致的。因此，我们可以用一个 set 来按顺序维护当前桌面上所有牌的初始序号。

同时，我们维护一个数组 $pos[x]$ ，用于记录数字为 $x$ 的牌当前在桌面上的初始序号。如果 $pos[x] == 0$ ，则说明当前桌面上没有数字为 $x$ 的牌。

当游戏进行到第 $i$ 回合，抽出数字为 $a_i$ 的牌时，按照以下逻辑处理：

放置：如果 $pos[a_i] == 0$ ，说明桌面上不存在相同的牌。我们将它的初始序号 $i$ 记录下来： $pos[a_i] = i$ ，并将其插入到 set 中。
消除：如果 $pos[a_i] \neq 0$ ，说明桌面上已经有这张牌，触发消除。此时手里这张牌直接丢弃，当前回合 $i$ 作为消除回合。我们需要在 set 中找到那张触发消除的牌的迭代器位置（利用 lower_bound）。从这个迭代器开始，向后连续遍历最多 $k$ 张牌（需注意迭代器不能越界）。对于被消除的每一张牌，我们将它的被消除回合记录为当前回合，将其在桌面上的标记清空（修改 $pos$ ），然后将其从 set 中删除。

时间复杂度为 $O(n \log n)$ 。当然本题用双向链表也是可以解决这个问题，具体维护方式和上面类似，这里不再赘述。

T5

100%

首先分析交互性质。当询问“ $x$ 评价 $y$ ”时，交互器的返回值存在以下真值表：

精明人评价精明人 $\rightarrow 1$
精明人评价糊涂人 $\rightarrow 0$
糊涂人评价精明人 $\rightarrow 0$ （实际是 $1$ ，由于说谎变成 $0$ ）
糊涂人评价糊涂人 $\rightarrow 1$ （实际是 $0$ ，由于说谎变成 $1$ ）

可以发现一个规律：如果 $x$ 和 $y$ 属于同一类人（同为精明人或同为糊涂人），一定会返回 1；如果属于不同类，一定会返回 0。

这意味着单次询问就能完美验证两人是否属于同一阵营。

我们可以固定向第 $1$ 个人询问剩下所有的 $n-1$ 个人。这样就将所有人分为了两个阵营：“与 1 同阵营”和“与 1 不同阵营”。题目保证精明人占多数（ $\ge \lfloor \frac{n}{2} \rfloor + 1$ ），所以人数较多的那个阵营一定全体都是精明人，另一个阵营则是糊涂人。

至此，我们只用了 $n-1$ 次询问就查清了所有人的真实身份。设初始糊涂人的总数为 $C$ 。题目要求从中挑选恰好 $k$ 个人进行反转。假设我们挑选了 $i$ 个糊涂人（使其变成精明人）和 $k-i$ 个精明人（使其变成糊涂人）。翻转后，糊涂人的总数为： $C - i + (k - i) = C + k - 2i$ 。此时的痛苦度为 $2^{C + k - 2i}$ 。

遍历所有合法的 $i$ （即 $0 \le i \le \min(C, k)$ 且 $k-i \le n-C$ ），计算对应的方案数：

\binom{C}{i} \times \binom{n - C}{k - i}

将方案数 $\times$ 对应的痛苦度累加即可。

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

# T6

100%

我们将每个节点的权值 $a_i$ 按二进制位独立处理，对于第 $b$ 位（ $0 \le b < 30$ ），问题转化为节点权值仅为 $0$ 或 $1$ 的树上组合求和。

对于三元组 $(i, j, k)$ 的最近公共祖先，设其为节点 $u$ 。此时 $w = \text{parent}(u)$ 。一个三元组的 LCA 为 $u$ ，当且仅当这三个节点都在 $u$ 的子树内，且这三个节点不全在 $u$ 的同一个子节点的子树内。

考虑容斥。设 $T(u, c)$ 表示在节点 $u$ 的子树中，选取三个不同节点且这三个节点的权值异或和为 $c$ （ $c \in \{0, 1\}$ ）的方案数。设 $u$ 的子树中权值为 $0$ 的节点数为 $C_0$ ，权值为 $1$ 的节点数为 $C_1$ 。

异或和为 $1$ 的方案（选择三个 $1$ ，或一个 $1$ 和两个 $0$ ）：$$T(u, 1) = \binom{C_1}{3} + C_1 \times \binom{C_0}{2}$$
异或和为 $0$ 的方案（选择三个 $0$ ，或一个 $0$ 和两个 $1$ ）：$$T(u, 0) = \binom{C_0}{3} + C_0 \times \binom{C_1}{2}$$

设 LCA 严格等于 $u$ 且子节点异或和为 $c$ 的合法三元组数量为 $H(u, c)$ ，可以用容斥求得：

$$H(u, c) = T(u, c) - \sum_{v \in \text{children}(u)} T(v, c)$$

最后根据到外部祖先父亲节点 $w$ 的权值 $v_w$ ，只有当 $c \oplus v_w = 1$ 时，这些三元组才会对当前第 $b$ 位的总答案有贡献。直接累加即可。

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

T7

100%

观察 $O(nk)$ 的 DP 状态转移：

如果第 $i$ 题不是数数题（即发生了清零）：当前方案对接下来的连续计数清零。 $dp[i][0] = \sum_{j=0}^k dp[i-1][j]$
如果第 $i$ 题是数数题：将延续之前的序列长度。$$dp[i][j] = dp[i-1][j-1] \times a_{i, j} \quad (1 \le j \le k)$$

我们可以将状态定义为一个 $1 \times (k+1)$ 的行向量 $S_i = [dp[i][0], dp[i][1], \dots, dp[i][k]]$ 。状态的转移可以用矩阵乘法表示： $S_i = S_{i-1} \times M_i$ 。其中转移矩阵 $M_i$ 是一个 $(k+1) \times (k+1)$ 的矩阵。具体如下：

第 $0$ 列的元素全为 $1$ （对应转移到 $dp[i][0]$ 的求和，矩阵下标从 $0$ 开始）。
对于第 $j$ 列（ $1 \le j \le k$ ），只有第 $j-1$ 行的元素值为 $a_{i,j}$ ，其余全为 $0$ 。

以 $k = 3$ 为例，状态向量有 $4$ 列，对应的转移矩阵 $M_i$ 如下：

$$M_i = \begin{bmatrix} 1 & a_{i,1} & 0 & 0 \\ 1 & 0 & a_{i,2} & 0 \\ 1 & 0 & 0 & a_{i,3} \\ 1 & 0 & 0 & 0 \end{bmatrix}$$

以此类推，最终答案的向量 $S_n = S_0 \times M_1 \times M_2 \times \dots \times M_n$。初始状态 $S_0 = [1, 0, \dots, 0]$ 。最终的总不满意度为 $S_n$ 向量所有元素的和。

当发生修改操作时，我们仅修改了某一个位置 $i$ 对应的矩阵 $M_i$ 中的单个元素。故我们可以利用线段树来维护矩阵的连乘积。最后计算 $S_n$ 的和即可。

总时间复杂度为 $O(n \cdot k^3 + q \log n \cdot k^3)$ 。