Codeforces Div.1 大合集

希斯塔的太阳永远不会落下！

PART I

恢复！恢复！

*1893 (Div. 1)

https://codeforces.com/contest/1893。

A. Anonymous Informant

考虑将 $b$ 序列还原成 $a$ 序列。一次移动后，移动的那个数一定跑到了序列的末尾，根据它还原即可。代码。

B. Neutral Tonality

答案的下界是 $a$ 的 LIS 长度，我们看看是否能够让答案就是这个。

由于 $b$ 可以随便加，因此将 $b$ 从大到小排序，这样能保证 $b$ 自身不会贡献 LIS 的长度。如果在 $a_i$ 前面扔一个所有数都比 $a_i$ 大的下降序列，那么此时将 $a_i$ 选进 LIS 里只可能比将下降序列的任何一个数选进 LIS 的长度更长，因此这样将 $b$ 扔进 $a$ 里一定不会使 LIS 变长。最后将剩余的 $b$ 扔到 $a$ 末尾，双指针合并 $a,b$ 即可。代码。

C.