万弘

2021-09-11 08:06 浙江大学 C++

关注

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

A

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

$O(n)$

My code

B

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

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

C

考虑 $x \text{ nxor }y=x\text{ xor }(y\text{ xor} 2^k-1)$
也就是每个数被操作前可以选择是否 $\text{ xor }$ 上 $2^k-1$ .而 $2^k-1\text{ xor }2^k-1=0$ 所以只需在不xor和xor一次中取max即可. $O(n)$

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

D

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

思路就是转成Kruksal重构树上LCA点权.LCA应该用 $O(n\log n)$ 或 $O(n)$ 预处理然后 $O(1)$ 查询.

My code

E

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

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

复杂度 $O(m\log n\log p)$ .exlucas很久没写了所以代码也就鸽掉了.

F

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

My code

全部评论

推荐最新楼层

Zxsoul

中国石油大学（华东） C++

%%%%

点赞回复分享

发布于 2021-09-11 08:42

06-27 14:56

河南工程学院 Java

释放一个wxg hc

转正offer终于来了🥹  赶紧跟wxg hr说拜拜（释放一个wxg的hc

点赞评论收藏

06-26 20:15

中央民族大学测试工程师

时间越长的实习含金量就越高吗

实习三个月和实习一个月 到底有什么区别？想知道一个月写简历上会不会被下一家公司问为什么只实习了一个月或者：实习两个月，学到了很多东西，可以简历上写三个月吗

点赞评论收藏

06-16 18:15

湖南人文科技学院 Java

求指点，投了两天 一个面试都没收到😅

湫湫湫不会java：1.在校经历全删了2.。这些荣誉其实也没啥用只能说，要的是好的开发者不是好好学生3.项目五六点就行了，一个亮点一俩行，xxx技术解决，xxx问题带来xxx提升。第一页学历不行，然后啥有价值的信息也没有，到第二页看到项目了，第一个项目九点，第二个项目像凑数的俩点。总体给人又臭又长，一起加油吧兄弟

点赞评论收藏