300iq Contest 1

rank solved A B C D E F G H I J K
67 4 . O O Ø ! O . . . . .

B

Solved by Henry.

注意到最小值必选,二分答案,树状数组做一个类似于 LIS 的 dp。

C

Solved by Henry.

$-1,0,1$ 三个数构造。

D

UpSolved by XLor.

权值从大到小枚举女生,判断是否存在一个完美匹配。使用霍尔定理进行判断,由于题目中女生区间没有包含关系,因此等价于枚举每一个连续子区间都能满足霍尔定理的条件。转化为前缀和,线段树维护即可。

E

UnSolved by XLor.

稀疏图的随机游走。

F

Solved by Henry.

一棵树不需要染色,于是原题等价于把删成一个森林,并查集即可。