ICPC 2018 World Finals 部分题解

注意

题解写得可能非常抽象。

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

A. Catch the Plane

题意

有 $0$ 到 $n-1$ 共 $n$ 个车站，你从 $0$ 出发，希望到 $n$ 。有 $m$ 趟公交车，每辆公交车从 $s$ 到 $t$ ，在时刻 $a$ 发车，时刻 $b$ 到站，有 $p$ 的概率存在。要赶一辆车，你要早于时刻 $a$ 到达站点 $s$ ；你只有尝试上车后才知道这班车是否存在。求最优策略下，最终能到达 $1$ 的概率。 $n,m\leq 10^6$ ，10s。

对于每个点，对于每个点记录若干条「若小于时刻 $x$ 到达此处，可以做到 $y$ 的到达 $1$ 的概率」，记作 $F$ 。按照发车时间从晚到早考虑所有车，在 $t$ 处二分出 $b$ 对应 $F$ ，结合 $a$ 处的 $F$ 的最后一项（或倒数第二项，如果最后一项的时间与 $a$ 相等），计算如果尝试坐这班车会不会提升概率，如果会的话就 push_back 到 $F$ 里面（如果最后一项的时间与 $a$ 相等，需要 pop_back 在 push_back）。

B. Comma Sprinkler

题意

给定一串单词，中间可能有句号和逗号。若一个单词前有逗号，则这个单词所有出现的位置前（若没有句号/不是开头）都要加逗号；单词后同理。求加完逗号的结果串。 $|S|\leq 10^6$ 。

题解

给每个单词建两个点，相邻的单词连边，代表某单词结尾有逗号时，另一单词开头必须有括号，反之亦然。然后 BFS/DFS 看哪些点可以从已有的逗号开始走到。

E. Getting a Jump on Crime

题意

有一个 $n \times m$ 的网格，每格有边长和高度。从给定格子出发，每次从一个格子的中心以 $v$ 的初速度沿抛物线跳到另一个格子的中心。求哪些格子可以到达，以及至少需要跳几次。 $n,m\leq 20$ 。

题解

小模拟。考虑判断一个格子能不能跳到另一个格子，可以先三分出到达目标位置位置时的最大高度及发射角，然后二分出恰好到目标位置、目标高度时的发射角，然后找到所有与路径相交的格子，确保路径比这些格子高。之后 BFS 即可。

H. Single Cut of Failure

题意

有一个正方形，其中有许多线段连接不同边上的两点。你要用尽可能少的直线与这些线段都相交。 $n\leq 10^6$

题解

首先，两条对角线一定能切所有的线段，问题变为能否用一条线切完。考虑将环破开，我们希望取一个区间的端点为黑色，使得所有线段都连接的是两个不同颜色的端点。从左往右扫区间左端的位置，区间右端会有许多限制，用线段树（set？）维护这些限制。

I. Triangles

题意

给定一个正三角形网格，有的边存在，有的边不存在。求图中有多少个三角形。 $n,m\leq 3000$ 。

题解

不妨考虑正立的三角形。先处理每个点往左上、右上能延伸多长。依次考虑所有极长的水平段，尝试使其作为底边：从左往右扫 / 边所在的直线，用树状数组维护哪些 \ 边可以延伸到与这条直线相交，每次查询这个的一个（由 / 边长度定义的）前缀。