DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

012

返回题目

题解

胜负分界 攻击者保证获胜所需的最少最坏比较次数为:

Q(N)=⌈3N2⌉−2.Q(N)=\left\lceil\frac{3N}{2}\right\rceil-2.Q(N)=⌈23N​⌉−2.

当 M≥Q(N)M\geq Q(N)M≥Q(N) 时选择攻击者,否则选择防守者。

攻击策略:上界 先找到两个不同值的代表 L<HL<HL<H,期间将相等的位置归为一组。一旦确认三个不同值的顺序,中间值必为 111。之后每个剩余位置只需与中间值的代表比较一次。

在尚未找到第三个值时,已处理的位置属于 L<HL<HL<H 两组。将两个新位置 a,ba,ba,b 一起处理,首先比较它们。

  • 若 a=ba=ba=b,将它们视为一组,与 LLL 比较,必要时再与 HHH 比较,总共不超过三次。
  • 否则重新命名使 a<ba<ba<b,并比较 aaa 与 。若 ,则由 确定中间值,再比较一次 与 即可。

每对位置最多需要三次比较,最后单独剩下的位置最多需要两次。因为三个值都出现,最终一定能找到第三个值。

设找到第一对不同代表前进行了 eee 次相等比较,最初的 e+2e+2e+2 个位置共消耗 e+1e+1e+1 次比较。令 R=N−e−2R=N-e-2R=N−,总次数至多为 。若提前找到中间值,剩余位置各需一次比较,因此不会增加此上界。

防守策略:下界 用并查集合并回答相等的位置,每个组的状态为未分类、低或高。维持所有严格比较都从低组指向高组。

  • 比较两个未分类组时回答不等,将一组标为低,另一组标为高。
  • 比较未分类组与低组时,回答未分类组更大并将其标为高。与高组比较时对称处理。
  • 比较两个不同的低组或两个不同的高组时,回答相等并合并。
  • 低组小于高组;已经属于同一组的位置回答相等。

若要使所有位置都已分类且仅剩两个组,分类全部 NNN 个位置至少需要 ⌈N/2⌉\lceil N/2\rceil⌈N/2⌉ 次比较,另需 N−2N-2N−2 次合并。这两类比较不重合,因此总共至少需要 Q(N)Q(N)Q(N) 次。

在此之前总能构造两个不同的合法序列。若有未分类位置且已有低、高组,可分别将(低、高、未分类)的值设为 (0,2,1)(0,2,1)(0,2,1) 与 (1,2,0)(1,2,0)(1,2,0)。若尚未进行比较,则任选两个不同的合法序列。若没有未分类位置,则低、高至少一侧有两个组。将另一侧固定为对应的极值,在这一侧选择两个不同组之一赋值为 111,其他组取该侧极值。两种构造都保留全部等式和严格大小关系。

因此当 M<Q(N)M<Q(N)M<Q(N) 时,该防守策略可以回答所有询问并提交两个证据序列。

判定与复杂度 评测程序的防守者采用上述策略。当只剩三个组,且再次合并同类型的两个组会导致只剩两组时,改为给这两个组确定严格顺序。此时三个组的值唯一确定。在此之前始终存在两个证据,因此交互程序能准确拒绝猜测。对于选手的防守策略,最终两个证据序列会与全部回答记录核对;有效证据也保证所有中间前缀的一致性。

攻击策略使用 O(N)O(N)O(N) 时间和空间。防守策略使用 O((N+M)α(N))O((N+M)\alpha(N))O((N+M)α(N)) 时间与 O(N)O(N)O(N) 空间。交互程序存储记录需要 空间。所有数值计算均在有符号 位整数范围内。

子任务 1 枚举 3N3^N3N 个序列中的合法序列,并以剩余序列集合为状态进行记忆化极小极大全搜索。状态数是指数级的,但 N≤6N\leq6N≤6 时足够小。子任务 2 使用上述策略。

Solution written by GPT6

LL
L
a<La<La<L
a<L<Ha<L<Ha<L<H
bbb
LLL
  • 若 a>La>La>L,则由 L<a<bL<a<bL<a<b 确定中间值,再比较一次原代表 HHH 与 aaa。
  • 若 a=La=La=L,比较 bbb 与 HHH。相等则并入原来的两组,不等则三个值均已确定。
  • e−
    2
    e+1+3⌊R/2⌋+2(R mod 2)≤Q(N)e+1+3\lfloor R/2\rfloor+2(R\bmod2)\leq Q(N)e+1+3⌊R/2⌋+2(Rmod2)≤Q(N)
    O(N+M)O(N+M)
    O(N+M)
    646464