牛客暑期多校训练4

来自PC Wiki
跳到导航 跳到搜索

Records

Contest

Solutions

A

离得最远的两关键点距离一半上取整,随便求.

B

建立线段树,利用线性基求交求出线段树每个结点上的答案

然后因为线段树上如果区间查询直接求交是三个$$\log$$的,但发现我们可以对$$\log$$段区间分别查询,这样就是两个$$\log$$的了

C

找出每个$$a_i$$当最小值的区间,然后对$$b_i$$的前缀和两边做一些RMQ.

卡常才是要紧的,当然你可以选择笛卡尔树...

D

答案只会是1或2,且分配方式仅与$$2^i\ mod\ 3$$的结果个数相关,做一下讨论即可

E

只关心$$a$$表示成的2的幂次里模3为1和2的个数.

考虑子集选数或出来是子集,发现很好算,那么全集就是关于这个做容斥.

F

考虑每次归并操作实际上是对一段一段排序(每一段为一个前缀最大数以及之后小于等于它的一段数)

然后我们用平衡树维护段,支持split和merge即可

G

H

I

考虑将翻转串接在正串后(中间加入分隔符),然后用SA求出本质不同子串

这些子串里需要减去跨分隔符的

然后发现回文串只被算了一次,其他算了两次

然后就用PAM求出本质不同回文串个数

J

分层图最短路裸题

K

做一遍前缀和,从前到后枚举i,当s[i+1]=s[i+2]='0'时对答案贡献为前缀和为s[i]的个数,加起来即可