2016-2017 CT S03E07: HackerEarth Problems Compilation

Problem A

Solved by ultmaster. 04:51 (+4)

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

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

所以为什么大家都是用自动机过的啊？

Problem B

Solved by zerol. 00:13 (+)

温暖的签到。

Problem C

Solved by ultmaster. 01:13 (+)

题意：找一个无向图里的小人。

题解：显然枚举中间那条边，但是两边用到的点不能重复。考虑求出和两边的点分别相邻的点 $l,r$ 和公共相邻的点 $s$，那么答案就增加 $\sum_{i=0}^3 \sum_{j=0}^2 \binom{l}{i} \binom{r}{j} \binom{s}{3-i,2-j}$。

Problem D

Solved by zerol & kblack. 02:30 (+5)

题意：给一个数列，每次询问两个区间内相同的数的对数。

题解：容斥拆成 4 个询问后莫队。

zerol：再问自杀。（死于复杂度写错，算错，平衡点找错，头铁，莫队排序写错）

Problem E

Solved by ultmaster. 00:16 (+)

排序签到。

Problem F

Solved by ultmaster. 03:31 (+1)

题意：$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$。

题解：枚举剩余系下的每一个数，是一条单调减的直线。要么第一个点就大了，要么总有一天会大。后面一种情况二分一下就好了。

Problem G

Solved by zerol. 04:01 (+)

题意：求范围在 a 和 b 之间的一个单调增数列数量，使得 LCM 是 d 的倍数。

题解：把 d 分解成若干个素数幂之积，然后容斥（有那几个素数幂炸了），再容斥（a 到 b 之间有多少个数被炸了），再用插板法计算一下方案数。

Problem I

Solved by kblack. 01:36 (+1)

题意：a 转化到 b，转化方式是加减质数，要求过程量全部都是质数。

题解：要么直接 +2 过去，要么从 2 中转，瞎几把判判。

Problem J

Solved by kblack. 03:49 (+4)

题意：给一个带点权的树，询问一条链，求点权和最大的子链。

题解：按是否跨过 LCA 分类，树上前缀和转化为最大差后，用倍增处理最大值最小值最大差，瞎几把合并，特判直接连接 LCA 的情况，合并两边。

Problem K

Solved by ultmaster. 02:12 (+)