本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-12 10:04:30

耻辱啊，E 题贪心假掉吃 3 发，F 题没处理跳过区间的 cases，最后 wa 3 个测试点，G 题简单题结果没看，掉大分了。

感觉每道题都弱于 CF 1900，但赛时确实因为各种原因没过 F,G。

E

我写了 3 种直接贪心的方式，都是错的。

1. 倒序枚举，遇到一个数，如果待匹配的集合内部存在一个数可以与之匹配，那么匹配最小的这个数。
2. 正序枚举，其余和上述一致。
3. 正序枚举，每次找到这个位置之后第一个能与自己匹配的，与之匹配。

考虑二分答案，设答案为 $k$。

显然选择前 $k$ 个和后 $k$ 个。

较为明显的，$1 \le \forall i \le k$，$i$ 个匹配 $n-(k-i)$ 个。

可以用类似于归纳法证明，第 $1$ 个元素需要匹配第 $n-k+1$ 个元素，如果不能匹配，则第 $[2,k]$ 个元素也不能与其匹配，而即使可以，第 $[2,k]$ 个元素匹配 $n-k+1$ 显然也不优。

随后问题就简化到了 $k-1$ 个元素的，得到证明。

F

只需要判断能否到达。

首先预处理出每个好区间 $[l,r]$，由于题目保证坏区间两两不相交，这个还是很容易的。

事实上，对于每个好区间 $[l,r]$ ，我们只关心 $[l,l+b]$ 和 $[r-b,r]$ 这个范围的位置能否到达。

如果 $a\neq b$，那么想要行走的距离 $len$ 足够大，就一定能走出这个距离。

那这个阈值如何计算呢？这个阈值小于等于使得 $xa+yb = len$ 无解的最大的 $len$，这刚好在 CCF 原题里面出现过，答案是 $ab-a-b$，代入 $a=19,b=20$ 得到这个无解的 $len$ 最大是 $341$，所以只需要处理 $len$ 在 $[0,341]$ 之间能否走出这个距离就可以。

对于 $a=b$ 的情况，只需要满足想要走的距离 $len$ 是 $a$ 的倍数就可以。

现在，设 $dp_{i,j}$ 代表第 $i$ 个好区间，左端点开始算第 $j$ 个位置能否被到达。设第 $i$ 个好区间是 $[l_i,r_i]$。

转移的话，先计算出 $[r_i-b,r_i]$ 区间哪些点可以到达。

随后，从 $[r_i-b,r_i]$ 区间的可以到达的点出发，枚举单次走的距离，更新后面区间的 $dp$ 值。

需要注意的是，这个过程可能会跳过一些区间。

比如，$3$ 个好区间 $[1,5],[7,10],[12,15]$，$a=b=8$，此时从 $5$ 出发将到达 $13$，跳过第一个区间直接到第 $3$ 个区间。

所以，不能简单的仅仅更新 $i+1$ 区间。

G

仍然沿用 E 题的 check 方法，仍然二分答案 $k$。

注意到对于第 $i$ 个位置，其作为较大值时，能匹配的位置是数组的一个前缀。

而合法的条件是对于 $(r-k+1) \le \forall i \le r$，第 $i$ 个位置向左最远的不可匹配的距离小于 $r-l+1-k$。

双指针预处理出每个位置作为较大值时，左边最远的不可匹配的距离，每次询问 ST 表就可以了。