CSP-S2022模拟赛3 10.16

CSP-S2022模拟赛3 10.16

A

移除受影响的数据后，最终序列是有序序列。

62782

B

直接考虑每种数字在每位出现次数即可。

注意考虑上下界边界情况。

62854

C [ARC102D] Revenge of BBuBBBlesort!

被操作的点仅可能是 $a_i=i$ 的点。

显然相邻且均满足 $a_i=i$ 的两个位置无法操作，所以原序列可分为若干交替是否满足 $a_i=i$ 的子串。

每个子任务单独考虑，必须满足 $a_i$ 在可交换的区间内且需要交换的数最长下降子序列长度不能超过 $2$。

90297746

D

考虑设 $f_{S,x,xi,y,yi}$ 表示已满足的限制的状态 $S$，从右往左正在满足的是 $x$，满足到 $xi$ 位，从左往右正在满足的是 $y$，满足到 $yi$ 位，最少的元素个数。

不妨从左向右考虑，对于所有向右得到的序列 $i$，若能接在 $y$ 后面，则满足 $y$ 的剩余部分可以被 $i$ 覆盖，于是之后只需要考虑 $i$ 即可。

对于 $x$，若已被填满，对于所有向左得到的序列 $i$，若可以接上，则满足 $i$ 的接入部分可以被 $x$ 覆盖，于是之后考虑 $i$ 的剩余部分即可。