1 条题解
-
0
思路
第一张截图中,只有作者的位置可能与真正顺序不同,其余成员的相对顺序已经完全确定。设这张截图的作者为 ,删去首位作者后得到序列 。所有可能的总顺序,都可以由把 插入 的某个间隙得到。
因此,问题可以转化为:是否存在一个插入位置,同时符合其余全部截图的要求。
做法
把 的位置从 开始编号,记录每位成员的位置 。设间隙编号 表示插入 后,在它前面的 中成员共有多少个,因此 。
对第一张之外的每张截图,先忽略首位作者。该作者与 不同,所以剩下的成员中一定包含 。
依次检查截图尾部:忽略 后,其余成员的 必须严格递增,否则这些成员之间的相对顺序与第一张截图矛盾。
如果一个成员 出现在 前面,就必须有 ;如果出现在 后面,就必须有 。将所有下界取最大、所有上界取最小。最终下界不超过上界时输出 YES,否则输出 NO。
当只有一张截图时,没有额外要求,至少一个间隙可用,因此一定可以。成员数量为 时,同样由初始区间 正确处理。
正确性证明
第一张截图删去作者后,恰好保留其他所有成员在总顺序中的相对位置。因此,任何可行总顺序都必须是把 插入 得到的。
固定某张其他截图。删去其作者及 后,剩余成员的相对顺序必须与 一致,这正是位置严格递增检查。对每个剩余成员,与 的先后关系分别等价于相应的间隙下界或上界。因此,该截图与某个总顺序一致,当且仅当位置检查通过且间隙满足该截图的全部界限。
所有截图同时一致,当且仅当它们的界限交集内存在一个整数间隙。所有界限均为整数,交集非空恰好等价于最大下界不超过最小上界。算法据此判断,结论正确。
部分分做法
子任务 1 可以枚举所有 种总顺序,对每张截图删去首位作者后逐一核对,相符时即找到可行解。
另一种等价建模是:每张截图删去首位后,将相邻成员连成有向边。所有截图能够同时成立,当且仅当此有向图无环。相邻边通过传递性表达整行顺序;无环图的任意拓扑序就是可行总顺序。
子任务 2 可以用邻接矩阵计算有向可达性的传递闭包,检查是否有顶点能够沿至少一条边回到自身。
子任务 3 只需要在邻接矩阵上进行三色深度优先搜索。当遇到当前搜索路径中的顶点时发现有向环;已搜索完的顶点不能误判为环。用显式栈代替递归可避免调用栈随长链增长。
也可以使用邻接表和入度剥离完成线性的拓扑排序。不同截图可能提供相同的边,应当同时保留重复邻接记录与相应入度,或同时对两者去重。
复杂度
插入间隙算法的时间复杂度为 。位置数组使用 空间;保存所有输入截图的本实现总空间为 。全文件的输入总量不超过 。
全排列枚举需要 时间;传递闭包需要 时间和 空间;稠密图判环需要 时间和 空间。邻接表拓扑排序则需要 时间与空间。
- 1
信息
- ID
- 1698
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者