HCW 19 Team Round

Problem A

Solved by Kilo_5723. 00:20 (+)

题意：三个人轮流在一个环上走，每个人走固定步数，求除起点外第一次有人踏上其他人走过的格子的时刻。

题解：模拟环上每个位置每个人第一次经过的时刻，对除起点外所有位置第二个人经过的时刻求最小值。

Problem B

Solved by Kilo_5723. 01:59 (+2)

题意：树上有一个宝藏，每次可以询问一个点到宝藏的距离，也可以询问一个点到宝藏路径上的下一个点，求宝藏位置。

题解：每次对树的重心询问到宝藏路径上的下一个点，以重心为根，只保留询问得到的点的子树，再对子树的重心如此询问，直到找到宝藏。

Problem C

Solved by Kilo_5723. 01:37 (+)

题意：直线上有一些位置有一些点，你有两种工具：第一种有 $p$ 个，可以覆盖 $w$ 的宽度，第二种有 $q$ 个，可以覆盖 $2 \cdot w$ 的宽度，每种工具都有数量限制，求最小的 $w$。

题解：如果工具总数超过了点数，那么答案是 $1$。否则，令 $dp_{(i,j)}$ 代表使用 $i$ 个第一种工具，$j$ 个第二种工具，从左到右最多能覆盖前 $dp_{(i,j)}$ 个点。$dp_{(i,j)}$ 可以从 $dp_{(i-1,j)}$ 和 $dp_{(i,j-1)}$ 转移，$dp_{(p,q)}$ 就是答案。

Problem D

Solved by Kilo_5723. 00:36 (+)

Problem E

Solved by Xiejiadong. 04:02 (+)

题意：需要完成 $n$ 系列攻击，每次攻击以后速度会减慢成 $b_i$ ，求最少的时间完成攻击。

题解：因为 $b_n=0$ ，完成攻击显然的策略是以最快的速度完成第 $n$ 次攻击，这样接下来的攻击都不会再花费时间。

我们用 $f[i]$ 表示完成第 $i$ 次攻击所需要花费的最少时间，于是可以很方便的得到 dp 方程 $f[i]=min_{1\le j\le i-1}f[j]+b[j]*a[i]$ 。

我们可以把 $k=b[j],b=f[j]$ 这样相当于每一次都产生一条新的一次函数，询问某一个 $x$ 处的最小值。

可以直接用李超树维护这部分的结果。

Problem F

Upsolved by Xiejiadong. (-7)

Problem G

Solved by Xiejiadong. 02:54 (+)

题意：询问第一棵无根树的最大深度是否大于第二棵无根树的最小深度。

题解：最大深度，可以通过先从任意节点作为根节点 dfs 一遍找到一个深度最深的点，然后以这个点为根在进行 dfs 找到最大深度得到。

最小深度，我们可以通过维护任意节点的有根数下每一个节点的最大深度和次大深度，再 dfs 一遍，将父亲方向的信息更新给孩子得到每一个节点作为根节点的时候的深度，取最小的作比较即可。

Problem H

Solved by Xiejiadong. 00:59 (+)

题意：顺次连接 $n$ 个块，使得连接起来的地方数字相同，给出任意方案。

题解：直接暴力枚举每一块的位置和摆放的方向，从前往后枚举，直接判断是否可行，不可行的直接剪枝。

Problem I

Solved by Kilo_5723. 02:48 (+)

Problem J

Solved by Xiejiadong. 00:28 (+)

题意：允许交换一个数的任意两位，求这些数中没有前导 $0$ ，小于原数，但最大的数。

题解：暴力交换出所有的情况，直接排序，找到答案。

Problem K

Solved by Kilo_5723. 03:50 (+1)

Problem L

Solved by Kilo_5723. 02:27 (+1)