CSP-S2022模拟赛3 10.16
CSP-S2022模拟赛3 10.16
A
移除受影响的数据后，最终序列是有序序列。
B
直接考虑每种数字在每位出现次数即可。
注意考虑上下界边界情况。
C [ARC102D] Revenge of BBuBBBlesort!
被操作的点仅可能是 a_i=i 的点。
显然相邻且均满足 a_i=i 的两个位置无法操作，所以原序列可分为若干交替是否满足 a_i=i 的子串。
每个子任务单独考虑，必须满足 a_i 在可交换的区间内且需要交换的数最长下降子序列长度不能超过 2。
D
考虑设 f_{S,x,xi,y,yi} 表示已满足的限制的状态 S，从右往左正在满足的是 x，满足到 xi 位，从左往右正在满足的是 y，满足到 yi 位，最少的元素个数。
不妨从左向右考虑，对于所有向右得到的序列 i，若能接在 y 后面，则满足 y 的剩余部分可以被 i 覆盖，于是之后只需要考虑 i 即可。
对于 x，若已被填满，对于所有向左得到的序列 i，若可以接上，则满足 i 的接入部分可以被 x 覆盖，于是之后考虑 i 的剩余部分即可。
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-10-17
，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录