1 条题解

  • 0
    @ 2026-11-15 21:16:44

    题目分析

    A. 自动化生产

    将 aa, bb, cc 连着三天记为一轮,先算出总共走的完整轮数 ⌊na+b+c⌋\left\lfloor\frac{n}{a + b + c}\right\rfloor,最后再算剩下的路程 nn % (a+b+c)(a + b + c) 需要走的天数 xx,最后答案为 3⌊na+b+c⌋+x3\left\lfloor\frac{n}{a + b + c}\right\rfloor + x。

    B. 书架平衡

    可以发现 hh 满足单调性(hh 越大花费越少),我们可以二分 hh,然后 O(n)O(n) 检查是不是符合条件。

    检查实现:

    • 对于每一个位置 ii,需要进行的消除次数是 ui+di−hu_i + d_i - h。
    • 为了满足 ∣ui−ui+1∣≤x|u_i - u_{i + 1}| \le x 的条件,ui+1u_{i + 1} 可行的范围是 [min⁡ui−x,max⁡ui+x][\min u_i - x, \max u_i + x]。
    • $\min u_i = \max(0, u_i - (u_i + d_i - h)) = \max (0, h - d_i)$ , max⁡ui=ui\max u_i = u_i。

    时间复杂度: O(nlog⁡(ui+di))O(n \log(u_i + d_i))​。

    C. 特工潜行

    对于每一轮操作,我们用数组维护若干个 [l,r][l, r],表示在当前轮操作完后,“夜影”特工可能到达的位置。初始化这个数组为 [m,m][m, m]。

    对于每一次操作,遍历每一对 [l,r][l, r] 进行更新

    • 如果 ai<la_i < l,那么操作后可能的区间为 [l−1,r][l - 1, r]。
    • 如果 ai>ra_i > r,那么操作后可能的区间为 [l,r+1][l, r + 1]。
    • 如果 l≤ai≤rl \le a_i \le r,那么操作后可能的区间为 [1,1][1, 1], [n,n][n, n],当 l<rl < r 时,还有区间 [l,r][l, r]。

    操作完排序统计个数即可。排完序后可以对于有交叉的 [l,r][l, r] 进行合并,减少后续操作的次数。

    乍看之下,该解法的时间复杂度似乎是 O(nq)O(nq),因为可能存在的区间数量会达到 O(n)O(n) 级别,且每个区间都需要更新。但通过观察可以发现,实际同时存在的有效区间不会超过 33 个:初始区间 [m,m][m, m](可向左右扩展)、最左端点 [1,1][1, 1](仅能向右扩展)以及最右端点 [n,n][n, n](仅能向左扩展)。

    时间复杂度: O(q)O(q),维护的区间数量为常数级别。

    D. 果园争锋

    对于果农 22,最优的操作是在剩余字符串还有 00 的时候,选 0101,否则选 1111。所以当两个果农刚好能一人选一次到游戏结束时,子串中一定满足 num0=3⋅num1num_0 = 3 \cdot num_1。

    • 当 num0≥3⋅num1+2num_0 \ge 3 \cdot num_1 + 2 时,果农 11 能在两人一人选一次后多选一次,玩家一获胜。
    • 当 num0<3⋅num1+2num_0 < 3 \cdot num_1 + 2 时,
      • 当 num0=3⋅num1−1num_0 = 3 \cdot num_1 - 1 时,在倒数第二轮选完之后,刚好只剩下两个 00、一个 11。果农 11 获胜。
      • 剩余其他情况下,带倒数第二轮选完之后会剩下两个 00 和若干个 11,果农 22 获胜。

    果农 11 获胜的数量就是所有满足的 num0−3⋅num1≥2num_0 - 3 \cdot num_1 \ge 2 或 num0−3⋅num1=−1num_0 - 3 \cdot num_1 = -1 的子串数量。

    设 cnticnt_i 表示前 ii 位的 num0−3⋅num1num_0 - 3 \cdot num_1 的数量,所有以第 ii 位结尾的子串中,果农 11 获胜的数量为满足 1≤j<i1 \le j < i 且 cntj≤cnti−2cnt_j \le cnt_i - 2 或 cntj=cnti+1cnt_j = cnt_i + 1 的 jj 的数量(满足 cnti−cntj≥2cnt_i - cnt_j \ge 2 或 cnti−cntj=−1cnt_i - cnt_j = -1,其中 cnti−cntjcnt_i - cnt_j 表示的是 (j,i](j, i] 的子串中的 num0−3⋅num1num_0 - 3 \cdot num_1 数量。

    最后只需要统计出满足 1≤j<i1 \le j < i 且 cntj≤cnti−2cnt_j \le cnt_i - 2 或 cntj=cnti+1cnt_j = cnt_i + 1 的 jj 的数量即可。

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

    本题考察了 DP,组合数学的相关知识。

    30pts

    我们用计数 dpdp。

    设 dpi,jdp_{i,j} 表示前 ii 个数,最后一个数是 jj 的合法方案数,转移:dpi,j=∑k≥jdpi−1,kdp_{i,j} = \sum_{k \geq j} dp_{i-1,k}。

    +30pts

    考虑 li=ljl_i=l_j,ri=rjr_i=r_j,假设 A=ri−li+1A=r_i-l_i+1,问题相当于求解值域 [1,A][1,A] 的不增序列,可以直接利用组合数插板法分析出答案。

    80pts

    上面两档分启发我们同时从 DP 和组合的角度考虑问题。

    用每个 Li,RiL_i, R_i 做分界点,把所有的数分组。

    设离散化的数组为 rere,则第 ii 组的数包括 [rei,rei+1)[re_i, re_{i+1})。

    这样我们可以愉快地 dpdp 了,设 dpi,jdp_{i,j} 表示前 ii 个数,最后一个数在第 jj 组的合法方案数。通过枚举 kk,表示 ak+1,⋅⋅⋅,ia_{k+1,···,i} 全在第 jj 组,进行转移:

    $$dp_{i,j} = \sum_{k=1}^{i-1} \sum_{p>j} dp_{k,p} \times \binom{len + i - k - 1}{len - 1}$$

    100pts

    这个内层求和显然可以用前缀和优化,所以总时间复杂度为 O(n3)O(n^3)。

    • 1

    信息

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