题解：P11172 「CMOI R1」mex2

Otomachi_Una_ · 2025-01-04 15:39:05 · 题解

神题。

考虑我们要不每个数都是 \infty，要么从 0,1,2,3,\dots 每个数只出现一次。

考虑这种构造：0,1,2,3,\dots,k,\infty,\dots,\infty,k+1,\infty,\dots,\infty。

这种构造能解决 c\leq \mathcal O(n^2) 的情况。

考虑更牛一点，我们把 0 挪到大概 t=\frac n3 的位置。然后你发现每次增量都是 t 的倍数，那我们强制在 a_n 填最大，再左边再填一个更大的就能得到余数了。

大概是这样子的：\infty\dots\infty,k+1,\infty\dots,\infty,0,1,2,\dots,k-1,\infty,\dots,\infty,k。

这样子构造就是 \mathcal O(n^3)。