竞赛讨论区 > 【题解】Wannafly挑战赛19
头像
牛客网小运营
编辑于 2018-12-27 14:50
+ 关注

【题解】Wannafly挑战赛19

(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)

T1 队列Q
将操作离线倒序处理理,可以线性效率解决这个问题。看代码很快就能懂了,不再赘 述。
时间复杂度:O(N + Q)

T2 矩阵
⾸先看一个问题:有一个长度为 N 的序列 A,对于每一个位置 i,计算以 i 位置为 结尾的最大⼦串和,且⼦串的左端点位置必须大于等于 Li 。数据保证 Li 是非递减 的。
设 Si 为 A 的前缀和,则以位置 i 为结尾的⼦串和为 Si − Sj ,在区间 [Li − 1, i] 内枚举位置 j 找到 Sj 的最小值就可以计算出以 i 为结尾的最⼤子串和。这个问题 利用单调队列是可以 O(N ) 解决的。
上述问题解决后,再来看这题: 可以枚举答案矩阵的上下边界,处理成一维的,题⽬中的第二个约束和第三个约束可以处理出 Li , 之后的问题就变成了上述那个问题了了。
时间复杂度:O(R ∗ C ∗ C )

T3 多彩的树
一棵 P 个节点的树中,路径数总共有 P + C 2 条。
将颜⾊进⾏行状压,Ti 表示颜⾊集合小于等于 i 的路径数量,计算 Ti 只要保留颜色
是状态 i 中的节点,求连通块后,每个连通子树计算方案数累加即可。
得到 Ti 之后,可以通过减去⼦集的路径数量,得到颜⾊集合恰好为 i 的路径数量。
时间复杂度:O(2K ∗ N )、

T4 回文
先考虑答案的来源:肯定是以某个位置为回⽂中心,留下最长回文半径,然后单边保留一些或不保留字符,然后砍掉多余部分,最后在另一侧补全,使得字符串成为回⽂串。
上述思路可以用 manacher 以及记录一些值的前缀后缀的最⼩值来实现。
时间复杂度:O(∣S∣)

T5 集合
这题代码量有一点大,容易写错,思路本身并不难。
costi,j 表示 A 集合的第 i 个元素和 B 集合的第 j 个元素,通过修改操作变换成相同的元素,需要的花费为 costi,j ,若⽆无法通过修改操作变成相同的元素,则costi,j 为 inf。costi,j 可以通过广度优先搜索来得到。
接下来就是一个二分图最小费⽤用匹配问题,可以用最小费用最大流来解决。 源点向 A 集合的每一个元素 i 建边,流量为 1,费用为 0。
B 集合的每一个元素 j 向汇点建边,流量为 1,费用为 0。
A 集合的每一个元素 i 向 B 集合的每一个元素 j 建边,流量为 1。如果 costi,j 为 inf,则费用为 dai + dbj ,表示这两个元素配对的⽅方式只能是两者都删除;如果 costi,j 不为 inf,那么费用为 min(dai + dbj , costi,j ∗ min(mai , mbj )),表示 这两个元素配对可以选择变换也可以选择直接删除,选择少的那一种费⽤用。
此外,在元素个数较少的那一侧,还需要新增⼀个节点 P ,⽤用来删除另一侧多余元 素。如果是 A 集合的元素⽐比 B 集合的元素少,那么源点和 P 之间建边,流量量为∣B − A∣,费用为 0;P 和 B 集合中的每⼀一个元素 j 建边,流量为 1,费用为dbj 。
上述图,从源点到汇点跑最小费⽤用最大流,跑出来的费用即为答案。 时间复杂度:O(N ∗ C 8 ∗ 162 + F ∗ V ∗ E),其中前半部分为 bfs 计算 cost的复杂度,后半部分为最小费用最大流的复杂度。

T6 K串
Si,j 表示前缀 [1, i] 中,第 j 种字母的数量对 K 取模的结果。每个位置的 Si 都可以看作是⼀一个 26 元组,每次询问就相当于询问区间 [L, R] 中有多少对相同的 26元组。
可以将 26 元组进行行 hash 成⼀一个数字或者可以将 26 元组插⼊字典树进⾏行操作。之 后就是《小Z 的袜子》了,利用莫队算法即可。
hash 做法的时间复杂度:图片说明
字典树做法的时间复杂度:图片说明

其他疑问可加以下交流群(加入一个即可啦~)
牛客多校算法训练营1:453799454
牛客全国算法训练营2:330766563
牛客多校算法训练营3:934889305

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐