竞赛讨论区 > 【题解】牛客挑战赛47

【题解】牛客挑战赛47

头像
Feecle6418
编辑于 2021-01-12 11:30:54 APP内打开
赞 2 | 收藏 2 | 回复4 | 浏览666
出了一些小锅,向大家道歉……
- 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 上线段树合并,求最长公共路径。复杂度同上。

4条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐