题解：P10370 「LAOI-4」Mex Tower (Hard ver.)

· · 题解

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

首先我们注意到，\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\}。