自动搬运

查看原文

来自洛谷，原作者为

	Breath_of_the_Wild 坐标 BJ XC ||

搬运于2025-08-24 22:57:18，当前版本为作者最后更新于2024-08-13 19:58:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷赛时的时候没做出来，没想到今天校内模拟赛就推出来了，特此写一篇题解。

首先我们注意到，$\operatorname{mex}\{a,b\}$ 一定为 $0$、$1$ 或 $2$，因为答案最多的情况就是 $a=0,b=1$，答案为 $2$。

于是序列算出来的结果不会超过 $2$。于是题面就变成了：给一个序列，按照题目要求模拟，最后结果是否为 $2$。只有这样所有的 $f(b)$ 才会一定 $\le f(a)$。

但是直接模拟会超时。于是考虑：什么样的序列操作完毕后为 $2$？可以从还剩一个数为 $2$ 的情况，倒推回还剩 $n$ 个数的情况回去。

我先举几个例子。倒推 $1$ 行，显然为了使结果为 $2$，这一行应该为 $0$ 和 $1$（注意翻转过去也可以）。再往前推一行，由于中间位置和两个数操作结果又有 $0$ 又有 $1$，故中间应该填一个 $\ge 2$ 的数。于是左边应填 $\ge 1$ 的数，右边应填 $0$。

以此类推，剩下的可以参考我画的这张图：

注意到当 $n$ 很大时，用到的只有中间的几个数，因为其他的位置可以随便填。

根据图片，进行分情况讨论：如果 $n$ 是奇数，只需要判断 $a_{\frac{n+1}{2}}\ge 2$ 且 $a_{\frac{n+1}{2}-1}\ge 1$ 且 $a_{\frac{n+1}{2}+1}=0$，或者 $a_{\frac{n+1}{2}}\ge 2$ 且 $a_{\frac{n+1}{2}-1}=0$ 且 $a_{\frac{n+1}{2}+1}\ge 1$ 即可（第二种情况是翻转，也可以）。

如果 $n$ 是偶数，只需要判断 $a_{\frac{n}{2}}=0$ 且 $a_{\frac{n}{2}+1}=1$ 且 $a_{\frac{n}{2}+1}=1$ 且 $a_{\frac{n}{2}+2}\ge 1$，或者翻转过来 $a_{\frac{n}{2}+1}=0$ 且 $a_{\frac{n}{2}}=1$ 且 $a_{\frac{n}{2}-1}\ge 1$ 即可。

另外，注意特判 $n=2$，因为 $n=2$ 时 $a$ 满足条件的只可能为 $\{0,1\}$ 或 $\{1,0\}$。