省选-真题练习

2016

P4093 [HEOI2016/TJOI2016] 序列

P4093 [HEOI2016/TJOI2016] 序列。

偏序问题我们可以转换成多维的 cdq 问题。

序列问题，我们设 $f_i$ 表示以 $i$ 为结束的最长子序列长度。

转移我们需要保证 $j$ 最大的比 $i$ 小，$i$ 最小的比 $j$ 大。

P5459 [BJOI2016] 回转寿司

P5459 [BJOI2016] 回转寿司。

比较水。不过注意范围 $r$ 需要保证 $a_r$ 比那个值小，用 upper_bound-1。

2017

P5365 [SNOI2017] 英雄联盟

P5365 [SNOI2017] 英雄联盟。

$f_{i,j}$ 表示前 $i$ 个，用了 $j$ 元。其实可以不用 $j$，然后背包。