1 条题解

  • 0
    @ 2026-11-15 21:38:32

    题目分析

    A. 魔法学院的传送阵

    • 如果 ss,tt 分别位于两座塔,只需要判断两个节点是否冲突即可。
    • 如果 ss,tt 位于同一座塔,那么需要在另一座塔中找到与这两个节点都不冲突的中间节点进行中转。这样的中转节点当 n≤2n \le 2 时一定不存在,当 n>3n > 3 时一定存在。
    • 注意特判 s=ts = t​ 的情况。

    B. 空间站调度

    • 对于第一种操作,只需要对每一艘飞船记录一个 fif_i,表示第 ii 艘飞船所在的空间站编号。
    • 对于第二种操作,
      • 要将所有 fi=af_i = a 的位置,变成 fi=bf_i = b。
      • 同时将所有 fi=bf_i = b 的位置,变成 fi=af_i = a。
      • 如果暴力地做,那么时间复杂度是 O(n)O(n),无法满足题目限制。
    • 可以发现 fif_i 的值跟最终的空间站编号存在一个对应关系,所以记录一个 posipos_i 来表示这个关系。初始化 posi=ipos_i = i,表示最开始每一个 fif_i 的值都表示对应的空间站。对于第二种操作,只需要更改对应的关系即可,即交换 posapos_a 跟 posbpos_b 的值。
    • 但此时第一个操作就不能直接赋值 fi=bf_i = b 了,而是要让 fi=jf_i = j(posj=bpos_j = b),所以要另外再记一个 idxiidx_i 作为跟 posipos_i 刚好相反的一个对应关系,方便进行操作一。

    在这样的情况下,

    • 操作一实际上就是让 fa=idxbf_a = idx_b。
    • 操作二实际上是要分别交换 (posidxa,posidxb)(pos_{idx_a}, pos_{idx_b}),跟 (posa,posb)(pos_a, pos_b)。
    • 操作三实际上是要输出 posfapos_{f_a}。

    时间复杂度: O(N+Q)O(N + Q)。

    C. 能量融合

    • 由于 Cnk≤106C_n^k \le 10^6,实际上的 min(k,n−k)≤10min(k, n - k) \le 10,因此可以直接搜索出每一种答案然后取最大值即可。
    • 对于 k>⌈n2⌉k > \lceil \frac{n}{2} \rceil,可以令 k=n−kk = n - k,最终答案为搜索出来的答案 XOR\text{XOR} a1⊕a2⊕⋯⊕ana_1 \oplus a_2 \oplus \cdots \oplus a_n。

    时间复杂度:O(2min(k,n−k))O(2^{min(k, n - k)})。

    D. 书架上的古籍

    1. 首先我们假定一个操作顺序 p1,2,⋯ ,np_{1, 2, \cdots, n}。
    2. 我们可以发现每一个古籍最多被操作两次。
      • 如果前面的书架还没有达到最大值,移动到前面的书架,总共操作 11 次。
      • 否则,先移动到最后一个书架,最后再在清空最后一个书架时前移,总共操作 22 次。
    3. 先清空所有 ai≤bia_i \le b_i 的书架,再清空 ai>bia_i > b_i 显然是最优的。当 (ax≤bx)=(ay≤by)(a_x \le b_x) = (a_y \le b_y) 时,如果位于 yy, xx 两个位置的书架要交换位置,必须满足 $\max(a_x, a_x + (a_y - b_x)) \le \max(a_y, a_y + (a_x - b_y))$,即让交换后要操作 22 次的书架数量减小。
      • 当 ai≤bia_i \le b_i 即 ai−bi≤0a_i - b_i \le 0 时,所以 $\max(a_x, a_x + (a_y - b_x)) \le \max(a_y, a_y + (a_x - b_y))$ 等价于 ax≤aya_x \le a_y。
      • 当 ai>bia_i > b_i 即 ai−bi>0a_i - b_i > 0 时,所以 $\max(a_x, a_x + (a_y - b_x)) \le \max(a_y, a_y + (a_x - b_y))$ 等价于 bx>byb_x > b_y。
    4. 统计答案时只需要记录需要进行两次操作的书架数量再加上所有书架的数量 ∑a\sum a。
    5. 统计两次操作的书架数量方法为,枚举 1≤i≤n1 \le i \le n,将第 pip_i 个书架作为最后清空的书架,需要进行 22 次操作的书架数量为
      • [1,i−1][1, i - 1] 每一堆书架清空操作时,需要进行 22 次操作的书架的数量以及
      • 删除第 ii 个书架以后,剩余书架按顺序消除时,消除到每一堆时需要进行 22 次操作的书架的数量的最大值。
    6. 维护一个前缀 $\text{pre}_i = \max(\text{pre}_{i - 1}, \text{prea}_i - \text{preb}_{i - 1})$,以及一个后缀 $\text{suf}_i = \max (\text{suf}_{i + 1}, \text{prea}_{i + 1} - \text{preb}_i)$。当 ∑b−bi≥∑a\sum b - b_i \ge \sum a 时,$\text{ans} = \sum a + \min_{i = 1}^{n}\max(\text{pre}_i, \text{suf}_i - (a_{p_i} - b_{p_i}), 0)$。

    E

    答案 =n−1−=n−1− 交集的最大值。

    对于每条边 ii,假设覆盖它的路径集合是 SiS_i,那么出现次数最多的 SiS_i 的出现次数就是交集的最大值。

    给每条路径随机一个 [0,263)[0,2^{63}) 内的权值,每条边的权值取成覆盖它的路径权值的异或和,利用树上差分即可。

    • 1

    信息

    ID
    202
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者