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)
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 (+)