CoderXL's Blog

Back

P10686 RochambeauBlur image

这题的“矛盾检测”是典型的扩展域并查集。

但是一个难点是,“裁判”的身份会改变矛盾的判断。如果一局有“裁判”参与,那么这局肯定是合法的。只有任为某一局没有裁判参与,才能通过并查集判断是否合法。

因此直接做会十分困难,我们需要转换为: O(n)O(n) 枚举裁判 再验证合法性。

当枚举 ii 为裁判时,直接忽略一切 ii 参与的对局。此时如果仍然出现矛盾,那么只能说明 ii 不是裁判或者 ii 不是唯一的裁判,即除了 ii 之外至少有一个人是裁判。

枚举所有的 ii,然后记录没有出现矛盾的次数 cntcnt. 如果 cntcnt00,那么没有人是唯一的裁判,输出 Impossible;如果 cntcnt 大于 11,那么有多个人都可以作为唯一的裁判,输出 Can not determine;只有 cntcnt 恰好为 11 时,能唯一确定某一个人是唯一的裁判。但这时候,我们需要输出判断所需的”最小轮数“。

这就是最传神的地方:一个轮数 rr 是能够判断 xx 是唯一裁判的最小轮数,意味着在 [1,r][1,r] 轮中,足以排除其他人是裁判的可能性,而在 [1,r1][1,r-1] 轮中不足以排除其他人是裁判的可能性。

这就是说,rr 就是枚举所有 ii 的时候,矛盾首次出现的轮数的最大值。

P10686 Rochambeau
https://blog.leosrealms.top/blog/oi/2026-04-17-p10686-rochambeau
Author CoderXL
Published at 2026年4月17日
Comment seems to stuck. Try to refresh?✨