胜负分界 攻击者保证获胜所需的最少最坏比较次数为:
当 时选择攻击者,否则选择防守者。
攻击策略:上界 先找到两个不同值的代表 ,期间将相等的位置归为一组。一旦确认三个不同值的顺序,中间值必为 。之后每个剩余位置只需与中间值的代表比较一次。
在尚未找到第三个值时,已处理的位置属于 两组。将两个新位置 一起处理,首先比较它们。
每对位置最多需要三次比较,最后单独剩下的位置最多需要两次。因为三个值都出现,最终一定能找到第三个值。
设找到第一对不同代表前进行了 次相等比较,最初的 个位置共消耗 次比较。令 ,总次数至多为 。若提前找到中间值,剩余位置各需一次比较,因此不会增加此上界。
防守策略:下界 用并查集合并回答相等的位置,每个组的状态为未分类、低或高。维持所有严格比较都从低组指向高组。
若要使所有位置都已分类且仅剩两个组,分类全部 个位置至少需要 次比较,另需 次合并。这两类比较不重合,因此总共至少需要 次。
在此之前总能构造两个不同的合法序列。若有未分类位置且已有低、高组,可分别将(低、高、未分类)的值设为 与 。若尚未进行比较,则任选两个不同的合法序列。若没有未分类位置,则低、高至少一侧有两个组。将另一侧固定为对应的极值,在这一侧选择两个不同组之一赋值为 ,其他组取该侧极值。两种构造都保留全部等式和严格大小关系。
因此当 时,该防守策略可以回答所有询问并提交两个证据序列。
判定与复杂度 评测程序的防守者采用上述策略。当只剩三个组,且再次合并同类型的两个组会导致只剩两组时,改为给这两个组确定严格顺序。此时三个组的值唯一确定。在此之前始终存在两个证据,因此交互程序能准确拒绝猜测。对于选手的防守策略,最终两个证据序列会与全部回答记录核对;有效证据也保证所有中间前缀的一致性。
攻击策略使用 时间和空间。防守策略使用 时间与 空间。交互程序存储记录需要 空间。所有数值计算均在有符号 位整数范围内。
子任务 1 枚举 个序列中的合法序列,并以剩余序列集合为状态进行记忆化极小极大全搜索。状态数是指数级的,但 时足够小。子任务 2 使用上述策略。
Solution written by GPT6