NOIP看题

cmaths · 2024-12-29 21:42:36 · 个人记录

T1T2在会考考场上想的……

T1

从特殊情况开始一顿分析，最终得到如下的贪心策略：

从前往后找到第一个能重排的位置，锁定此区间，看一下右端点有没有另一个序列的区间，之前的所有可以等效为不能重拍

太抽象了不好讲

T2

容易知道，会发生冲突当且仅当由一个位置一直推到了另外一个位置，方案数乘起来就好了