QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: GotoHiotori

Posted at: 2026-06-29 20:40:46

Last updated: 2026-06-29 21:23:25

Back to Problem

「不超过 $5n$ 的做法」详细揭秘 yyc 为什么是神

前情提要

来详细揭秘下 yyc 老师的做法:

首先我们得知这样一件事:已知 $a\leq b$ 时询问 $\{a,b\},\{c\}$ 可以得到 $a=0,b\leq c$ 或者 $c\leq b$。

我们先询问 $0,1$ 大小关系,把大的放在第一行而小的放在第二行。

接下来:

每次选两个不确定也不被写出的数 $a,b$,先问一次 $\{a\},\{b\}$ 把它调到 $a\leq b$。

然后记当前第一行末尾是 $c$,询问 $\{a,b\},\{c\}$,如果得到 $a=0,b\leq c$ 就确定下 $a$ 然后直接把 $b$ 扔回未确定的部分,否则在第一行末尾写上 $b$,第二行末尾写上 $a$。

这样你经过所有操作后剩下两行各有 $l$ 个元素(以及你可能还有一个未确定元素 $x$),其中第一行是不降序,且对于每个 $i$ 都有第二行第 $i$ 个不大于第一行第 $i$ 个。

如果存在那个多余的 $x$ 的话你先拿它和第一行末尾比较大小留下较大的写在第一行,然后你现在对每一列两个元素都花费了本应确定出一个元素的 $5$ 代价,你希望你能只再用不超过 $5$ 的代价确定出这两个。

那具体来说,如果大的那个是 $0$ 的话你不需要问就能知道小的是 $0$。

于是你顺着扫 $i$,每次问第一行第 $i$ 个与第 $i+1$ 个的和是否比最大值(也就是 $1$)大,第一次取到 $>$ 的 $i$ 不确定,但是第一行 $i$ 后面确定全都是 $1$ 了,于是你已经确定了各花费 $3$ 代价扫过的前 $i-1$ 列,这部分费用没超,然后你也确定了第 $i+1$ 列及以后的第一行都是 $1$,这些列还有 $5$ 次可以花费去确定第二行,然后第 $i$ 列浪费了 $3$ 代价但还什么都没确定出来,然后你对于剩下没确定的 $2(l-i+1)$ 个元素恰好花费 $5(2(l-i+1)-1)-2$ 的代价用那个取两个和 $1$ 比较下留一个的算法求出来($-2$ 是因为你知道第 $i$ 列那两个元素的大小关系,当然如果有那个多余的 $x$ 还得多花 $5$,然后多余的 $x$ 时你也多花了 $2$ 来确定最大值),精细计算是恰好不超过 $5n$ 次的,应该能取到但是懒得思考构造了。

submission

Comments

No comments yet.