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 的剩余部分即可。

62999