牛客练习赛88 A~F 题解(E仅口胡)
牛客练习赛88 A~F 题解(E仅口胡)
A
不考虑位数的限制直接5555..5111..1即可.有位数的限制时将多余的1从前往后放即可.
B
法一:大力hash.这是可以的,但稍微麻烦一些,没有用到的性质.
法二:考虑取出child串的最后个字符记为
,那么合法的条件是从mother种删去一个长度为
的子串
,满足
且剩余的两端拼起来=child串.预处理child每个前缀和后缀(删去
后)能和mother匹配的最长长度,中间
个暴力比较即可,
.
My code
C
考虑
也就是每个数被操作前可以选择是否上
.而
所以只需在不xor和xor一次中取max即可.
(俺代码写的稍微麻烦了一些)
My code
D
我做过原题:最小瓶颈路.
思路就是转成Kruksal重构树上LCA点权.LCA应该用或
预处理然后
查询.
E
缝合题.
第一部分类似动态图连通性,用线段树分治+可撤销并查集维护,或离线LCT.
第二部分在于合并两个连通块怎么计算贡献.这个组合数没有什么高明的方法只能exlucas.
复杂度.exlucas很久没写了所以代码也就鸽掉了.
F
建出广义SAM之后随便怎么暴跳一下就行,复杂度是经典的,会广义SAM就该会了.去重可以容斥或暴力bitset.
