自己会做ABCDEFG,主要是这场 Edu 太水了,做起来和 Div3 感觉一样。。

A

选择第一个,第二个和最后一个。判断是否可行即可。

B

显然每次都会选择最长的 $1$ 的连续段。模拟即可。

C

设前缀和为 $s_i$。一个区间合法的条件是 $s_r-s_{l-1} = r-(l-1)$,推一下式子是 $s_r-r = s_{l-1}-(l-1)$,直接 map 记录一下就好了。

D

每次肯定会取出两个最大的,所以从大到小排序后dp记录一下每一维选了多少个即可。

E

想一想大概是假设现在有 $k$ 个加倍牌,我们会选出来最大的 $k$ 个让它加倍,但是要特判一下最大的 $k$ 个都是加倍牌的情况(这个时候要从不加倍牌找一个最大的替换掉加倍牌种最小的),注意每次询问前 $k$ 大的数中 $k$ 的变化$O(1)$,两个set维护即可。

F

先预处理出 $f_i$ 表示 $i$ 结尾最长的区间,满足这个区间可以通过填充 ? 变成值都相等的区间。

然后我们在计算 $x$ 的答案的时候可以从 $n$ 开始跳:每次往前跳到距离它最近的满足 $f_i \geq x$ 的位置即可。

可以发现如果每次找到跳到的位置的复杂度是 $O(k)$,发现复杂度就是 $O(kn \ln n)$ 的(因为可以发现每次跳的区间长度 $\geq x$,所以跳的次数 $\leq \sum_{i=1}^n \frac{n}{x}=O(n \ln n)$。

如果使用 set 实现,复杂度为 $O(n \log^2 n)$,过不了。

思考一下我们把 $x$ 从小往大枚举,每次相当于删除一些点,问一个点最前面没被删的点是啥,可以用链表/并查集维护。就过去了。

G

本质上只需要做询问是否有周长为 $d$ 的矩形。

$y$ 是固定的,相当于问你是否有一组 $(i,j)$ 满足 $x_i-x_j = d$,FFT 即可。

Last modification:September 4th, 2020 at 09:16 pm
如果觉得我的文章对你有用,请随意赞赏