1 条题解

  • 0
    @ 2026-9-9 22:22:46

    思路

    第一张截图中,只有作者的位置可能与真正顺序不同,其余成员的相对顺序已经完全确定。设这张截图的作者为 cc,删去首位作者后得到序列 bb。所有可能的总顺序,都可以由把 cc 插入 bb 的某个间隙得到。

    因此,问题可以转化为:是否存在一个插入位置,同时符合其余全部截图的要求。

    做法

    把 bb 的位置从 00 开始编号,记录每位成员的位置 pospos。设间隙编号 gg 表示插入 cc 后,在它前面的 bb 中成员共有多少个,因此 0≤g≤n−10\le g\le n-1。

    对第一张之外的每张截图,先忽略首位作者。该作者与 cc 不同,所以剩下的成员中一定包含 cc。

    依次检查截图尾部:忽略 cc 后,其余成员的 pospos 必须严格递增,否则这些成员之间的相对顺序与第一张截图矛盾。

    如果一个成员 vv 出现在 cc 前面,就必须有 g≥posv+1g\ge pos_v+1;如果出现在 cc 后面,就必须有 g≤posvg\le pos_v。将所有下界取最大、所有上界取最小。最终下界不超过上界时输出 YES,否则输出 NO。

    当只有一张截图时,没有额外要求,至少一个间隙可用,因此一定可以。成员数量为 11 时,同样由初始区间 [0,0][0,0] 正确处理。

    正确性证明

    第一张截图删去作者后,恰好保留其他所有成员在总顺序中的相对位置。因此,任何可行总顺序都必须是把 cc 插入 bb 得到的。

    固定某张其他截图。删去其作者及 cc 后,剩余成员的相对顺序必须与 bb 一致,这正是位置严格递增检查。对每个剩余成员,与 cc 的先后关系分别等价于相应的间隙下界或上界。因此,该截图与某个总顺序一致,当且仅当位置检查通过且间隙满足该截图的全部界限。

    所有截图同时一致,当且仅当它们的界限交集内存在一个整数间隙。所有界限均为整数,交集非空恰好等价于最大下界不超过最小上界。算法据此判断,结论正确。

    部分分做法

    子任务 1 可以枚举所有 n!n! 种总顺序,对每张截图删去首位作者后逐一核对,相符时即找到可行解。

    另一种等价建模是:每张截图删去首位后,将相邻成员连成有向边。所有截图能够同时成立,当且仅当此有向图无环。相邻边通过传递性表达整行顺序;无环图的任意拓扑序就是可行总顺序。

    子任务 2 可以用邻接矩阵计算有向可达性的传递闭包,检查是否有顶点能够沿至少一条边回到自身。

    子任务 3 只需要在邻接矩阵上进行三色深度优先搜索。当遇到当前搜索路径中的顶点时发现有向环;已搜索完的顶点不能误判为环。用显式栈代替递归可避免调用栈随长链增长。

    也可以使用邻接表和入度剥离完成线性的拓扑排序。不同截图可能提供相同的边,应当同时保留重复邻接记录与相应入度,或同时对两者去重。

    复杂度

    插入间隙算法的时间复杂度为 O(nk)O(nk)。位置数组使用 O(n)O(n) 空间;保存所有输入截图的本实现总空间为 O(nk+n)O(nk+n)。全文件的输入总量不超过 200000200000。

    全排列枚举需要 O(n! nk)O(n!\,nk) 时间;传递闭包需要 O(n3+nk)O(n^3+nk) 时间和 O(n2)O(n^2) 空间;稠密图判环需要 O(n2+nk)O(n^2+nk) 时间和 O(n2)O(n^2) 空间。邻接表拓扑排序则需要 O(nk+n)O(nk+n) 时间与空间。

    • 1

    信息

    ID
    1698
    时间
    2000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者