【题解】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