How to AK ABC388

· · 题解

耻辱啊，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 表就可以了。