CF896B Ithea Plays With Chtholly 做题记录

桌子上面摆着 $n$ 张白纸，交互库会依次给你 $m$ 个 $[1,c]$ 中的数，你每次可以把所获得的数写在一张纸上或者替换掉某一张纸上写的数，在你行动结束后交互库才会给你下一个数。任何时候，如果所有纸上都写了数字并且成非降序排列，你就赢了，直接结束程序。你要想办法赢交互库。

$2\le n,m$，$1\le c\le 1000$，$1\le n\cdot \lceil\frac{c}{2}\rceil\le m\le 1000$。

首先给出构造方法：

• 若 $x\le \lfloor\frac{c}{2}\rfloor$，那么从左到右找到第一个满足 $a_i=0$ 或 $a_i>x$ 的 $i$ 放入 $x$；
• 若 $x>\lfloor\frac{c}{2}\rfloor$，那么从右到左找到第一个满足 $a_i=0$ 或 $a_i<x$ 的 $i$ 放入 $x$；

接下来证明这个构造方法，首先考虑这样一条引理：

• 若每次都从左到右找到第一个满足 $a_i=0$ 或 $a_i>x$ 的 $i$ 放入 $x$，那么最终的单调不降序列长度至少是 $\lceil\frac{m}{c}\rceil$；

证明：

考虑这 $m$ 个数中出现次数最多的数 $v$，由于值域大小为 $c$，所以根据抽屉原理，$v$ 至少会出现 $\lceil\frac{m}{c}\rceil$ 次。

把这 $m$ 个数分成三部分考虑：

• 满足 $u=v$ 的 $u$，这些 $u$ 构成的单调不降序列长度至少是 $\lceil\frac{m}{c}\rceil$；
• 满足 $u<v$ 的 $u$，显然这些 $u$ 都出现在所有 $v$ 之后是最坏情况，这时这些 $u$ 均会被 $v$ 代替；
• 满足 $u>v$ 的 $u$，显然这些 $u$ 都出现在 $v$ 之前是最坏情况，这时这些 $u$ 均会被 $v$ 代替；

所以最坏情况下最终的单调不降序列长度也是 $\lceil\frac{m}{c}\rceil$，得证。

回到我们的构造方法，设满足 $x\le \lfloor\frac{c}{2}\rfloor$ 的 $x$ 有 $t$ 个，那么满足 $x>\lfloor\frac{c}{2}\rfloor$ 的 $x$ 则有 $m-t$ 个。根据引理，易得出满足 $x\le \lfloor\frac{c}{2}\rfloor$ 的那 $t$ 个 $x$ 构成的单调不降序列长度至少是 $\lceil\frac{2t}{c}\rceil$，其它的 $x$ 构成的单调不降序列长度至少是 $\lceil\frac{2(m-t)}{c}\rceil$，由于 $\lceil\frac{2t}{c}\rceil+\lceil\frac{2(m-t)}{c}\rceil\ge \lceil\frac{2m}{c}\rceil\ge n$，所以得证。