Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)

本文最后更新于:星期四, 二月 3日 2022, 9:15 晚上

A. XORinacci

签到

B. Uniqueness

题意:删除一个最短的子串,使得剩下的数字唯一出现

思路:枚举左端点,右边不断向左扩展。

C. Magic Grid

题意:构造一个nnn\cdot n的矩阵,里面填入0n210-n^2-1,使得每行每列异或和都相同。

思路:对于每个444\cdot 4的矩阵都构造出

0123456789101112131415 \begin{matrix} 0 & 1 & 2 & 3 \\ 4 & 5 & 6 & 7 \\ 8 & 9 & 10 & 11\\ 12 & 13 & 14 & 15 \end{matrix}

D. Restore Permutation

题意:给出一个序列,aia_i 的权值是满足j<i&aj<aij<i \& a_j<a_iaja_j和,现在给出权值,问原序列

思路:倒过来求,在权值线段树上二分

E. Let Them Slide

题意:有nn个滑块,滑块长度不同,每个滑块第ii列有权值,单独求每列的和的最大值。

思路:multisetmultiset维护第ii列可选取的滑块,维护即可。