2020牛客暑期多校训练营（第二场）

All with Pairs

求

其中表示的前缀可以匹配的后缀的最长长度。

考虑，先对后缀，求出某个值的后缀有多少个，用存。

然后对每个字符串求一个前缀，计算匹配的个数，然后乘以长度的平方。

但是有一个问题，有一些部分是重复计算的。

比如

我们算的时候会把的贡献也算进去，所以要减去的贡献。

具体来说就是求一个数组，把重复计算的部分删去。

code

Boundary

因为圆要固定过原点，然后枚举剩下两个点，利用三个点确定圆心，用记录圆心坐标。

code

Cover the Tree

这题数据好像有点水，不少水做法都可以过。

我们考虑 u 的子树，如果 u 的子树有两个以上的节点，那么选择两个配对，配对之后删除，不然就加入到 u 的节点里面，可以利用一次 dfs ，从低向上更新就行了。

code

Duration

签到题，把时间都转换为秒，然后求一个差的绝对值就好了。

code

Fake Maxpooling

求所有 k*k 的子矩阵的最大值之和。

我们可以利用两次优先队列求矩阵的最大值，先对行压缩，再对列压缩。

code

Greater and Greater

优化dp

有一个长度为n的A串，和长度为m的B串，求A有多少个子串大于B。

先预处理出

把每一位对齐之后发现只有当某一列全为1的时候才表示当位是符合的情况，那么我们可以考虑用一个bitset来与每一个串，若满足第m-1位为1则有解。

code

Just Shuffle

求出所有的循环节，对于每个循环节，求出在下的逆元，

然后将循环节滚动次。

code