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

题意：一个平面上有 $n$ 个点，求以 $(x,y)$ 为圆心，半径为 $r$ 的圆里，从圆心出发能看到多少点。

题解：先筛出圆内的点，再对角度去重。

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

题意：$n$ 堆石子，两个人轮流取石子，有两种操作：可以从任意一堆里拿走一个，也可以在所有石子堆非空的情况下从每堆拿走一个，没有石子可拿的人输，求谁能获胜？

题解：如果没有第二种操作，那么石子总数的奇偶就决定了胜者。

如果石子堆的数量是奇数，第二种操作和第一种操作在奇偶性上没有区别，胜者依旧取决于石子总数的奇偶。

如果石子堆的数量是偶数，此时如果最小的石子堆有奇数个石子，那么先手必胜。否则仍是石子总数的奇偶决定胜者。

Problem J

Solved by Xiejiadong. 00:28 (+)

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

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

Problem K

Solved by Kilo_5723. 03:50 (+1)

题意：一个排好序的质数数列，每个数小于 $10^4$，每次可以询问 $\prod_{i=l}^r a_i \;{\rm mod}\; 10^9+9$，要用 $<0.45$ 的总代价求出数列每个元素的值。

题解：因为是排好序的，知道两个元素的乘积就能求出两个元素的值。询问每一个长度为偶数的前缀的区间乘积，如果长度小于一半就用总乘积乘上另一半的逆元。然后再依次求出每对数。

如果数列长度是奇数就减去一个，最后用总乘积乘上除去最后一个数的逆元。

Problem L

Solved by Kilo_5723. 02:27 (+1)

题意：有 $n$ 个位置，每个位置上有一个数，可以花 $A$ 的代价从 $i$ 到 $i+1$，花 $B$ 的代价从 $i$ 到 $i-1$，花 $C$ 的代价到一个数字与当前位置相同的位置，求两点间的最短距离。

题解：对每一类数，新建一个结点，这类数到它连一条 $C/2$ 的双向边，再跑最短路。