ICPC 2021 World Finals 部分题解

注意

题解写得可能非常抽象。

「如果一个题解你看不懂，那是题解垃圾而不是你垃圾。」

B. Dungeon Crawler

题意

有一棵 $n$ 个点的树，边有长度， $q$ 次询问，给定点 $s,k,t$ ，分别代表起点、钥匙所在的点、陷阱所在的点。你要从起点出发，用尽量短的时间遍历过所有点，但要求到达陷阱点之前必须经过过钥匙点。 $n\leq 2000, q\leq 2 \times 10^5$ 。5 s。

题解

每次询问 $O(n)$ 求解（可以通过提前计算 DFS 序、避免递归等减小常数）。

显然，答案应当是选择一个最深的叶子 $l$ ，将其作为最后到达的点，从而它到根的链上的边只用经过一次，而其他边需要两次。但如果这个点在 $\operatorname{lca}(k,t)$ 的 $k$ 所在的字数中就有问题了，因为这个子树不能简单地放到最后访问。我们需要：

$\operatorname{lca}(k,t)$ 外面的点，先正常遍历完。
到 $\operatorname{lca}(k,t)$ 时，先进 $k$ 所在的子树，把整棵子树遍历完，但是在 $\operatorname{lca}(k,l)$ 处，不往 $l$ 所在的子树里面走。
回到 $\operatorname{lca}(k,t)$ ，遍历其他所有子树。
再回到 $\operatorname{lca}(k,t)$ ，走到 $\operatorname{lca}(k,l)$ ，遍历 $l$ 所在的子树，并最后停在 $l$ 。

注意到从 $\operatorname{lca}(k,t)$ 到 $\operatorname{lca}(k,l)$ 的部分一共会经过三次。求解是为了方便，可以直接在计算深度时，把 $k$ 到 $\operatorname{lca}(k,t)$ 这一部分边的权值当做负的，代表它们反而会使答案增加一倍边权。

$n$ 个人分 $m$ 块钱。他们要先确定一个数 $0<f<1$ ，第一个人拿走 $m$ 块钱的 $f$ 倍，第二个人拿走剩下的钱的 $f$ 倍，……，第 $n$ 个人拿走剩下的钱的 $f$ 倍，第一个人拿走剩下的钱的 $f$ 倍……最后每个人都会拿到一个收敛的钱数。求 $f$ 使得每个人拿到的钱数都是整数或判断无解。优先最小化 $f$ 的分母，其次最小化 $f$ 的分子。 $6\leq n\leq 10^6, m\leq 10^18$ 。

题解

设 $1-f = a/b$ 且 $(a,b)=1$ ，则每个人拿的钱是 $f^k/(1-(a/b)^n) m$ ，简单通分和因式分解后，要求为 $(a^{n-1} + a^{n-2}b + \cdots + b^{n-1})|m$ 。 $b$ 不可能很大，枚举即可。

F. Islands from the Sky

题意

平面上有 $n$ 个多边形，每个 $n_k$ 个点。现在希望从空中拍摄这些多边形。有 $m$ 条航线，每条是空间中的一个线段；飞机沿航线飞行时会使用相机拍照，拍摄范围为底边与航线垂直、整体与地面垂直、顶点为飞机位置、顶点角度为 $2 \theta$ 的等腰三角形，对应到平面上是一个线段；飞行一段之后扫过的即为一个等腰梯形。求 $\theta$ 至少是多少，才能保证每个多边形都至少被一条航线完全拍摄到，或者判断无解。 $n,m,n_i\leq 100$

题解

二分 $\theta$ 。多边形被一条航线完全拍摄到等价于每个顶点都被这条航线拍摄到；判断时只需要求出这个点在【线段在平面上投影】的投影位置的比例（从而求出对应的飞机高度，从而求出扫过范围的宽度），以及这个点到【线段在平面上投影】的距离。

H. Prehistoric Programs

题意

有 $n$ 个小括号构成的字符串，求一个方案，将其拼接成一个合法括号序列，或者判断无解。字符串长度和 $10^7$ 。

题解

考虑左括号为 $+1$ ，右括号为 $-1$ ，则每个串要求前缀和不小于一个数，如果满足就可以接上它并让和加上另一个数。这是经典的「如果血量不小于 XXX 就可以打怪，打怪可以获得 XXX 血量」的问题。排序，净加分为正的排在前面，负的排在后面；对于正的，右括号少的排在前面；对于负的，左括号多的排在前面。排完序之后检查一遍。

I. Spider Walk

题意

有一个蜘蛛网， $n$ 条从中心向外的射线， $m$ 条两节相邻射线上（相同模长）的点的边；每条边对应的模长各不相同。蜘蛛从中心出发，沿着射线 $s$ 向外走，遇到边就爬过去，这样最终会到达某条射线。对于每条射线 $i$ ，求从 $s$ 出发，要最终到达 $i$ ，至少要添加多少条边。 $n\leq 2\times 10^5, m\leq 5\times 10^5$ 。

题解

考虑从内往外，一边考虑每条边，一边维护每根射线的需要边数，这个边数的差分一定是 $0,-1,1$ 。遇到一条边，会将两条射线的需要边数交换，然后每条射线要和相邻射线边数加一取 $\min$ ，注意到这个操作至多改变 $O(1)$ 处边的差分，找到修改位置需要求某点开始向左/右最长的差分全 $-1$ / $1$ 的延伸距离。用 set 维护哪些差分是 $0$ 、是 $1$ 、是 $-1$ ，最后得到差分数组后，从答案是 $0$ 的射线开始推即可还原出答案。往集合里面同时放 $i,i-n,i+n$ 可以简化实现。

J. Splitstream

题意

有 $n$ 个序列处理机，共两种：

输入两个序列，一左一右地取，归并成一个新序列，输出。
输入一个序列，一左一右地分配到两个序列，输出。

这些处理机接起来，每个输出至多用作一次输入。有一个初始序列 $a$ 为 $1$ 到 $m$ 可能多次用作输入。多次询问某份输出的第 $k$ 个元素。 $n\leq 10^4, m\leq 10^9, q\leq 10^3$ 。