1 条题解

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

    题目分析

    • 考虑动态规划,观察发现:操作能除去草和位置无关,所以先将草的高度排序。
    • 每次操作除去比最高草的高度的一半低的草,最坏情况就是只能除一株草,也就是次高的草是最高草的高度的一半,设最高草的高度为 (h),那么最多操作次数为 (\log_2(h)) 次,约为 30。
    • 状态定义:(dp_{i,j}) 表示除去前 (i) 株草操作 (j) 次的最小提前除草次数。
    • 状态转移:
    • 除去第 (i) 株草有两种方法:
      1. 提前除草:(dp_{i,j} \leftarrow dp_{x,j-1});
      2. 操作除草:(dp_{i,j} \leftarrow dp_{i-1,j} + 1)。
    • 所以最后的转移方程就是 (dp_{i,j} \leftarrow \min(dp_{i-1,j-1}, dp_{x,j} + 1))。其中 (x) 是低于第 (i) 株草高度一半的草中最高的草最大的下标(可以用二分求)。
    • 最后答案只要遍历操作次数,遇到一个有答案的 (i) 就直接输出 (i) 和 (dp_{n,i})。
    • 时间复杂度:O(nklog⁡n)O(n k \log n)​。

    5

    20pts O(n3q)O(n^3q)

    问题相当于求解两两点对之间的最短路距离,乘上一个权重后的结果。

    考虑对于每次询问,使用 Floyd\text{Floyd} 算法在 O(n3)O(n^3) 的时间复杂度内求解两两点对之间的最短路距离,总复杂度为O(n3q)O(n^3q)。

    60pts O(n2q)O(n^2q)

    对于第 uu 天,答案显然为 $\sum_{1 \leq i,j \leq n} c_{i,j} \times \text{dist}'(i,j)$ 其中 dist′(i,j)\text{dist}'(i,j) 表示将对应路径的边权设为 00 以后 (i,j)(i,j)​ 的最短路。

    先跑出原图两两点之间的最短路 dist(i,j)\text{dist}(i,j)。

    假设在这一天,清零的道路为 (x,y)(x,y),那么对于点对 (i,j)(i,j),其变化的路径权值为 $\max(0,\text{dist}(i,j)-\text{dist}(i,x)-\text{dist}(y,j),\text{dist}(i,j)-\text{dist}(i,y)-\text{dist}(x,j))$ 即讨论是否走过 xi,yix_i,y_i 这条道路,从而更新修改后的图的最短路,时间复杂度为 O(n2q)O(n^2q)。

    100pts O(n3+q)O(n^3+q)

    上述式子等于 $\max(0,\text{dist}(i,j)-\text{dist}(i,x)-\text{dist}(y,j))+ \max(0,\text{dist}(i,j)-\text{dist}(i,y)-\text{dist}(x,j))$ 考虑如何证明,即说明 dist(i,j)−dist(i,x)−dist(y,j)\text{dist}(i,j)-\text{dist}(i,x)-\text{dist}(y,j) 和 dist(i,j)−dist(i,y)−dist(j,x)\text{dist}(i,j)-\text{dist}(i,y)-\text{dist}(j,x) 不能同时大于00,我们利用反证法,假设二者同时大于 00,那么将两式相加,有 $2\text{dist}(i,j)>\text{dist}(i,y)+\text{dist}(y,j)+\text{dist}(i,x)+\text{dist}(x,j)$ 而由于最短路的性质,有 $\text{dist}(i,j) \leq \text{dist}(i,y)+\text{dist}(y,j)$

    $\text{dist}(i,j) \leq\text{dist}(i,x)+\text{dist}(x,j)$

    两式相加,和上面的式子矛盾,所以成立。

    问题变成了如何求解 $\sum_{1 \leq i,j \leq n}c(i,j) \times\max(0,\text{dist}(i,j)-\text{dist}(i,x)-\text{dist}(y,j))$ 固定 ii 后将所有 dist(i,x)\text{dist}(i,x) 从小到大排序,然后枚举 j,yj,y,可以利用双指针快速计算所有答案,时间复杂度为O(n3+q)O(n^3+q)​​。

    • 1

    信息

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