日记

沟槽的构造题。

今天早上打 VP，直接被构造题创飞，于是开始练习构造。

好像练了 dp 就只会 dp 一样。其实 dp 也不够会，其他都不会做。

Arcology On Permafrost# Link to

考虑 $f(a)$ 的最大值。首先一定有 $f(a) \le n - m \times k$，因为一个序列的 $\operatorname{MEX}$ 不可能大于它的长度。还有 $f(a) \le \lfloor \frac{n}{m + 1} \rfloor$，因为为了在 $m$ 次里，每个数都有剩的，每个数的出现次数必须大于 $m + 1$。

考虑如何构造：

• 当 $n - m \times k < \lfloor \frac{n}{m + 1} \rfloor$，那么我们有 $i \in [0,n),a_i = i \bmod k$，这样可以保证无论删掉哪几个子串，最后都会有 $a_i = i$，使得 $\operatorname{MEX}$ 最大。
• 当 $n - m \times k \ge \lfloor \frac{n}{m + 1} \rfloor$，我们可以构造 $i \in [0,n),a_i = i \bmod \lfloor \frac{n}{m + 1} \rfloor$。这样可以保证相同的数字之间至少有 $k$ 的距离，每个数还有至少 $m + 1$ 个。

Happy Birthday! 3# Link to

神金区间 dp。

自己写的 solution

后日谈 # Link to 后日谈

自己抓了一点构造题来练，我连黄的构造题都做不太出来我还去做蓝色的构造题，我扯吧我。

忽然发现今天好像就做了这几道题，也是十分的颓废。