牛客练习赛88 A~F 题解(E仅口胡)

A

不考虑位数的限制直接5555..5111..1即可.有位数的限制时将多余的1从前往后放即可.

My code

B

法一:大力hash.这是可以的,但稍微麻烦一些,没有用到的性质.

法二:考虑取出child串的最后个字符记为,那么合法的条件是从mother种删去一个长度为的子串,满足且剩余的两端拼起来=child串.预处理child每个前缀和后缀(删去后)能和mother匹配的最长长度,中间个暴力比较即可,.
My code

C

考虑
也就是每个数被操作前可以选择是否上.而所以只需在不xor和xor一次中取max即可.

(俺代码写的稍微麻烦了一些)
My code

D

我做过原题:最小瓶颈路.

思路就是转成Kruksal重构树上LCA点权.LCA应该用或预处理然后查询.

My code

E

缝合题.
第一部分类似动态图连通性,用线段树分治+可撤销并查集维护,或离线LCT.

第二部分在于合并两个连通块怎么计算贡献.这个组合数没有什么高明的方法只能exlucas.

复杂度.exlucas很久没写了所以代码也就鸽掉了.

F

建出广义SAM之后随便怎么暴跳一下就行,复杂度是经典的,会广义SAM就该会了.去重可以容斥或暴力bitset.

My code