【题解】牛客挑战赛47

出了一些小锅,向大家道歉……
- A 的题面出了些问题。
- 评测机太快把 F 暴力放过去了……我自己写的暴力都会 T 所以以为没事,但大家常数确实优秀
- 本场比赛所有题目时限都在标程两倍以上(除了 F),G std 900ms 开了 2s,E 验题人 1.2s,std 2.6s 所以开的 4s,但好像确实有选手被卡常,非常抱歉

以下是题解。

## T1:一道 GCD 问题

求出差分数组的 GCD,这个 GCD 就是原数组的 GCD 的最大可能值。只需要让 $a_1$ 是这个数的倍数就能取到最值。

## T2:又一道 GCD 问题

对每个 $a_i$,枚举其约数 $j|a_i$,$cnt[j]++$。选 $k$ 个的答案为 $cnt[j]$ 大于等于 $k$ 的最大的 $j$。直接做是 $O(n\sqrt{a_i})$,可以优化到 $O(a_i log a_i)$。

## T3:条件

可能存在的边假如全都存在时都还不可能 $i\to j$ 那么 $i$ 一定不能走到 $j$,否则就有可能可以。用 bitset 优化,$O(\dfrac{n^3}{w})$。

##T4:Lots of edges

所有满足起点的权值、终点的权值相同的都是本质相同的,可以合并计算。这样,本质不同的边只有 $O(3^17)$ 条,可以直接枚举。用枚举补集子集的方法即可不重复不遗漏。
最后用 BFS 计算答案即可。一个易错点在于要特判 $a_i=a_S$ 的情况,若 $i=S$ 输出 $0$,若 $a_S=0$ 输出 $1$,若 $i\ne S$ 且 $a_i\ne 0$ 且 $S$ 有边连出则输出 $2$,否则输出 $-1$。复杂度 $O(3^{17}+n)$。

## T5:路径

点分治求长度 $=k$ 的路径条数再前缀和然后二分回答询问。然后发现每轮的答案统计是卷积,可以用 NTT 实现。模数需要选取得足够大才能保证正确性。复杂度 $O(S \log S \log n+n \log n)$。( $S$ 为所有边权之和)

## T6:简单题

可以把积性函数拆开($\mu(ij)\ne 0$,因此 $i,j$ 互质)莫比乌斯反演,最后得到的式子可以 $O(n \log n)$ 暴力算。容易用 Dirichlet 前缀和优化到 $O(n \log\log n)$。

## T7:子串

- 法一:对 S 建 SAM、T 建PAM,SAM 上线段树合并维护转移边,PAM 上倍增预处理父亲。对于每个 T 的位置 i,找到 PAM 上 i 的节点和结尾为 i 的与 S 匹配的最大长度 now,用倍增找到 PAM 上最深的 x,满足 len[x]<=now,用 len[x] 更新答案。时间复杂度 $O(|S| \log |S|+|T| \log |T|)$。
- 法二:对 S,T 都建 PAM,然后在 PAM 上线段树合并,求最长公共路径。复杂度同上。

全部评论
T4有 17*2^17 的做法,前置知识SOSdp(一开始以为3^17会被卡没敢冲233)
2 回复
分享
发布于 2021-01-09 22:33
E这份代码就离谱 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46436960 E题你要保证总复杂度是两个log的话,需要在点分的时候按子树深度排序从小到大合并才能保证严格两个log的复杂度吧……否则是可以构造出数据卡掉的 比如你根和 1条1e4的边连,再连4e4个长度1的边,你第一次直接合并1e4的边,之后每次卷积都要卷1e4,做4e4次就炸了。 感觉题解中应该提到保证严格SlogSlogn的方式而不是一笔带过吧
2 回复
分享
发布于 2021-01-10 14:49
小红书
校招火热招聘中
官网直投
E的std 2.6s,现场选手的暴力O(n^2)只需要1.9s 😆 太欢乐了吧
2 回复
分享
发布于 2021-01-11 11:11
naive 这个G好卡常/dk
点赞 回复
分享
发布于 2021-01-10 07:31

相关推荐

5 2 评论
分享
牛客网
牛客企业服务