1 条题解

  • 0
    @ 2026-11-15 19:27:48

    题目分析

    情(friendship)题解

    题意抽象出来就是:给定一张 nn 个点 mm 条边的无向连通图,qq 次询问 [l,r][l,r] 中有多少整数 ww 满足存在一条从点 11 到点 xx 的长度为 ww 的路径。保证边权只有 1,21,2 两种。

    首先来考虑如果只有边权为 11 的边怎么做,其实就是经典的奇偶最短路,可以参考 [CSP-J2019] 加工零件。对于每个 xx 先求出 11 到 xx 的长度为偶数的最短路 dx,0d_{x,0} 和长度为奇数的最短路 dx,1d_{x,1},那么通过在 11 权边上左右横跳我们就能够构造出所有长度为 dx,0+2kd_{x,0}+2k 和 dx,1+2kd_{x,1}+2k 的路径(kk 为自然数),又因为不可能有路径的长度比这两个值更小,所以这实际上就是所有可能的路径长度。

    注意到这个做法的关键在于抓住一条 11 权边左右横跳,使得所有比 dx,0d_{x,0} 大的偶数都能被得出(奇数同理)。那对于有 22 权边的情况,奇最短路经过的边里肯定有 11 权边,所以不会受到影响;但是偶最短路却有可能仅由 22 权边组成,此时”左右横跳“的调整就只能做到 +4k+4k 而非 +2k+2k,会漏掉一部分偶数。为了应对这种情况,我们只需要额外求出至少经过一条 11 权边的偶最短路,这个也是好做的,类似最短路拓展到奇偶最短路,在跑奇偶最短路时额外记录一维 0/10/1 表示目前有没有走过 11 权边即可。这一部分的复杂度视最短路的实现而定,如果用堆优化 Dijkstra 复杂度为 O(nlog⁡n)O(n\log n)(默认 n,mn,m 同阶)。 回答询问时,奇数部分是一个公差为 22 的等差数列,偶数部分是公差分别为 2,42,4 的两个等差数列求并,可以通过简单的分类讨论以 O(1)O(1) 的复杂度完成。

    • 1

    信息

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