2016-2017 Codeforces Trainings Season 3 Episode 7(CT S03E07)

Problem A

Upsolved by Xiejiadong.

题意：给 $n$ 个串，有两种操作，一种是给某个串加一个字符，另一种是求存不存在一个串是查询串的子串。强制在线。

题解：由于限制了总长，所以不同的长度不会太多（根号级别）。枚举长度匹配一下哈希就行。

自动机也是能搞的，但是没有hash写起来舒服。

Problem B

Solved by Kilo_5723. 00:10(+)

温暖的签到题。

Problem C

Solved by Kilo_5723. 00:50(+)

题意：给定一个没有重边的图，求此图中一共有多少给定火柴人形状的子图。

题解：观察这个火柴人，我们发现七个点中，其他五个点都连在剩下的两个点上。因此，枚举中间相连的两个点，接下来分别判断它们分别是上半身和下半身中点的情况。

对于剩下所有的点，有四种情况：两个点都不连接，连接上半身的点，连接下半身的点，和两个都连接。

对于第一种情况，无需讨论。对于第二种情况，只要讨论下半身的剩下两个点在后两种情况中怎么取，就可以求出方案数。对所有方案数求和就是答案。

Problem D

Solved by Weaver_zhu && Kilo_5723. 03:43(+)

题意：给出 $m$ 个询问，每个询问给出 $l_1,l_2,r_1,r_2$，求由多少个二元组 $(i,j)$ 使得 $l_1<=i<=r_1,l_2<=j<=r_2,a_i=a_j$

题解：从 $f(l_1,r_1,l_2,r_2)$ 到 $f(l_1+1,r_1,l_2,r_2)$ 等曼哈顿距离为1的询问是可以 $O(1)$ 转移的，加上或者减去改变的数作为二元组其中一个点即可。然而四维还不能直接使用莫队，需要用容斥转化成二维查询。$dp[i][j]$ 表示 $1$ 到 $i$，$1$ 到 $j$ 两个区间的询问，则 $solve(l_1,r_1,l_2,r_2)=dp[r_1][r_2]-dp[l_1-1][r_2]-dp[r_1-1][l_2]+dp[l_1-1][l_2-1] $。

Problem E

Solved by Xiejiadong. 00:20(+)

题意：给第一匹马找一个匹配，询问是否存在第一匹马的匹配代价大于其他所有的匹配。

题解：贪心。显然给第一匹马找最大的匹配。

其余的肯定是最大的和最小的匹配，依此类推。

直接排序，暴力判断即可。

Problem F

Solved by Xiejiadong. 03:23(+8)

题意：$f_i = f_{i-1} + a_{i \bmod n}$, $f_0 = 0$; $g_n = h - \frac{n(n+1)}{2}$。求第一个 $n$ 满足 $f_n \ge g_n$。

题解：$f_i$分别变成$f_i+i$可以在保证$|f_i-g_i|$不变的情况下，把$g_i$矫正成直线。题目变成询问$f_i$的前缀和第一个超过常数$g$的位置。

二分判断在哪一个周期超过了常数$g$，判断的方法是找一个周期的最高点。

对于第$x$个周期，前$x-1$个周期的前缀和可以直接得到，然后暴力计算本周期的前缀和，判断最大的是否超过了常数$g$。

对于第一个超过的周期，暴力寻找位置即可。

这道题目会爆long long，然后各种玄学的方法来调整判断，于是自闭了。

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Solved by Weaver_zhu. 02:10(+12)

题意：给出两个素数 $a,b$ ($a,b\le 10^{15}$),求出只包含加减运算的的运算步骤，且中间值和加或减的数均为素数。

题解：奇数加奇数为偶数，而只有2不是奇数，所以运算的情况是相当少的。同时一个数最多加2两次，否则 $x,x+2,x+4$ 模3的值均不同，有一个一定不是素数。如果一个数是奇数，则它只能加减2，或者是减到2。如果一个数是2，则它可以加或减到b-4~b+4。判素数应该使用Miller-Rabin，由于之前没怎么用过就被红书的板子坑了（大概是素数没选对，数据会卡。

Problem J

Upsolved by Kilo_5723.

题意：给定一棵树，每一个节点上有一个或正或负权值，现在每次访问两个节点，问这两个节点路径上的点权和最大的非空子路径的点权和是多少。

题解：$LCA$。用倍增法维护并合并一条竖直方向路径的三个元素：含有顶节点的最大子路径点权和，含有底节点的最大子路径点权和，和普通的最大子路径点权和，最后再合并两条从访问节点出发到其 $LCA$ 的向上路径。

Problem K

Solved by Kilo_5723. 04:44(+)

题意：有一列长度为 $n$ 的火车，求一共有多少种 $k$ 个颜色的染色方案，使得恰好有 $t$ 种方案选出长度为 $d$ 的颜色相同的一段车厢。

题解：首先，我们发现，如果一共有 $l$ 段相同颜色段，一个染色方案的选出车厢的方案数为 $\sum_{i=1}^{l} length_i$。

我们设 $dp[i][k]$ 代表第 $i$ 个车厢结尾有 $k$ 种方案选出的染色数，我们发现，除了只有一段的情况，$dp[i][k]=\sum_{j=1}^{d-1} dp[i-j][k]+\sum_{j=1}^{k} dp[i-d+1-j][k-j]$。我们发现，这是一段折线段，而拐点所在列是 $i-d+1$ 。因此，我们每次处理一列 $i$，之后将拐点列上的 $dp$ 元素从平线加到斜线上，即可在 $O(n*t)$ 的时间内求出答案。