专栏文章

题解：P14134 【MX-X22-T5】「TPOI-4E」Get MiN? Get MeX!

yyemuzhe
P14134题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minq24xt
此快照首次捕获于
2025/12/02 06:29
3 个月前
此快照最后确认于
2025/12/02 06:29
3 个月前
查看原文
确定性，太困难。
这是一种非确定性算法，期望询问次数 log⁡n+O⁡(1)\log n + \operatorname O (1)。
首先观察一下 3535 大概是 log⁡\log 级别，考虑二分。
二分就是每次把当前集合分成大小为 ⌊n2⌋\left \lfloor {n \over 2} \right \rfloor 和 ⌈n2⌉\left \lceil {n \over 2} \right \rceil 的两部分，保留一部分，舍弃另一部分。
假设当前集合中没有 11，那么 00 所在部分的第一类询问就会返回 11，而另一部分的第一类询问就会返回 ≥2\ge 2。
所以大概想法就是，在第一次二分中把 11 给踢出去。
具体地，在第一次二分中不断把集合随机分成大小为 ⌊n2⌋\left \lfloor {n \over 2} \right \rfloor 和 ⌈n2⌉\left \lceil {n \over 2} \right \rceil 的两部分，直到大小为 ⌊n2⌋\left \lfloor {n \over 2} \right \rfloor 的部分的第一类询问返回 11 为止。
上述过程后，一定能够保证 00 和 11 在不同的集合中，否则第一类询问会返回 ≥2\ge 2。成功概率 121 \over 2，期望次数为 22 次。
在这之后，还需确定 00 在哪一部分。
这时候可以对某一部分分别问一次第一类操作和第二类操作，返回值相等说明 00 在另一部分，反之则在这一部分。
在第一次二分之后，每次二分若第一类询问返回 11 则保留该部分，否则保留另一部分，直到剩下的集合大小为 11 为止。
第一次二分期望 2+1+1=42 + 1 + 1 = 4 次，之后每次二分只需 11 次，总期望 log⁡n+O⁡(1)\log n + \operatorname O (1)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...