传送门
Table of Contents
感觉今年题目貌似比 去年 简单，是我的错觉吗？（反正几何题大家都不会去开的）。
还是按照我认为的难度排序。。。
Problem H. Prehistoric Programs
贪心乱搞。
Problem A. Crystal Crosswind
我们需要找出必须是 ‘#’ 的点和必须是 ‘.’ 的点，剩下的可以随便填。
考察每组 wind 能够给出的信息：
(1): 首先对于其中的每组 (x, y) boundary，(x, y) 必然填 ‘#’，且 (x – wx, y – wy) 必然填 ‘.’。
(2): 除此之外，对于每个不在 boundary 的点 (x, y)，也是能给出一定信息的（风大概还有个 z 轴从上向下吹的。。），要么 (x, y) 是 ‘.’ 要么 (x, y) 是 ‘#’ 且 (w – wx, y – wy) 也为 ‘#’。
其实就是 floodfill … 具体实现的时候，对于第一问，先假设所有点都是 ‘.’，然后根据 boundary 信息给出初始的 ‘#’，然后再对于每一个新的 ‘#’，用第二个条件去做 floodfill 填出其它的 ‘#’。
第二问的做法也类似，记得还要考虑边界外的 ‘.’。
Problem L. Where Am I?
因为我们要求和，所以只能暴力 bfs()，就是和前几天 CF 的那个题差不多，开两个队列来回倒腾，把所有源点弄成一个集合塞进队列里，然后每次移动一步，边移动边分拆集合，直到集合中只有 1 个元素，复杂度 O(n4)。
考虑到标记的规模只有 O(n)，所以另一种做法是，我们预处理出每个点，到每个标记的距离，对这些距离按照字典序排序，就可以得到最早被分割的时间（结构类似后缀树组），复杂度 O(n3logn)。
Problem I. Spider Walk
I 题开始题目读错了。。以为是可以花费 1 的代价修 bridge，然后求单源最短路。。。但是实际上对于每一个弦（bridge）。。。只要遇到了，就是必须经过的。。。
那最后就是在这个东西上面 dp 。。。dp 的过程相当于，从远到近，每次加一些弦。。然后用这些弦去做松弛。。。每添加一条边，实际上是交换这两个点的状态，然后再分别向左和向右一路扫下去。。
2 3 3 2 1 0 1 2 3 2 1 0 1 1 1 2 2 1 0 1 2 1 2 1 1 0 1 2 2 1 1 1 0 1 2
以样例 1 来说的话。。dp 状态是这样。。考察第一条边加入之后，虽然交换了 dp[4], dp[5] 的值，但是 dp[6] 依然等于 1，因为我们再后续添加边时，可以决定添加边的顺序。。。
所以每个状态在任意时刻，除了交换的时候，dp 值不会变劣，确实符合 ”松弛“ 的一般定义。。。
最后只要动态离散化压缩 dp 状态即可。。。
Problem B. Dungeon Crawler
正解要倍增祖先 + dp，感觉非常难写。。。但是这个题可以 O(nq) 搞过去囧（想不到吧。。。
不过去年的 B 题都能 O(n2) 爆过去囧，这个当然也不算什么。。。。
Problem C. Fair Division
初始有 m 价值的金子，n 个海盗围成一圈，每次当前金子的 p/q 留给自己，剩余的给下一个人，这个过程将无限进行下去。
问是否能找到合法的 p, q 使得每个海盗获得金子的极限是整数（中间可以是分数）。。。
貌似很久以前 GCJ 出过一次海盗分金。。。这个题看起来推理过程要简单一些。。。
基本思想是先列出每个海盗分得黄金的等式，用简单的数论知识找到判别式，最后再用一些代数技巧估计 q 的上界，暴力枚举（或许，你也可以跳过这个步骤。。直接卡时）。
$$\begin{equation}
\begin{split}
& mf\sum_{i=0}^\infty r^i \newline
& r = (1 – f)^n \newline
& f = \frac{p}{q} \newline
\end{split}
\end{equation}$$
$$\begin{equation}
\begin{split}
mf\sum_{i=0}^\infty r^i & = \frac{mf}{1-r} \
& = \frac{mf}{1-(1-\frac{p}{q})^n} \
& = \frac{mf}{1-(\frac{q-p}{q})^n} \
& = \frac{mf}{(\frac{q^n-(q-p)^n}{q^n})} \
& = \frac{mfq^n}{q^n-(q-p)^n} \
& = \frac{mpq^{n-1}}{q^n-(q-p)^n} \
& = \frac{mpq^{n-1}}{q^n- \sum_{i=0}^{n}q^i(-p)^{n-i}\binom{n}{i}} \
& = \frac{mpq^{n-1}}{\sum_{i=0}^{n-1}q^i(-p)^{n-i}\binom{n}{i}} \
& = \frac{mq^{n-1}}{-\sum_{i=0}^{n-1}q^i(-p)^{n-1-i}\binom{n}{i}}
\end{split}
\end{equation}$$
上面的 q^{n-1} 和分母是互素的，因此在判定整除时可以直接忽略。
具体来说，如果 a, b 互素，那么 a^n – b^n 与 a 和 b 都互素。证明可以反证法，假设存在素因子，推出 a 和 b 不互素即可。。。
利用这个结论，不仅可以简化判别式，还可以发现任意考察哪个海盗都一样。。。。
上式还可以继续二项式展开。。。
$$\begin{equation}
\begin{split}
\frac{mp}{q^n-(q-p)^n} & = \frac{mp}{q^n- \sum_{i=0}^{n}q^i(-p)^{n-i}\binom{n}{i}} \
& = \frac{mp}{-\sum_{i=0}^{n-1}q^i(-p)^{n-i}\binom{n}{i}} \
& = \frac{m}{\sum_{i=0}^{n-1}q^i(-p)^{n-1-i}\binom{n}{i}}
\end{split}
\end{equation}$$
我们发现上面的 p 因子也可以消去。。。
进一步我们可以使用不等式对上式进行放缩，或者直接把 n 最小的情况往里面代入，得到 q 的上界即可。
其实我觉得还是挺难的囧。
Problem G. Mosaic Browsing
算法导论告诉我们，Rabin Karp 算法可以非常容易的将字符串匹配推广到矩形上（其实就是 Hash 乱搞），但是我们很快发现此题真正要处理的难点是通配符。
学习了例题之后我们发现只要用 FFT 就可以有效的解决这个问题了~！而且只有模式串有通配符。。判别式还要更简单一些。
似乎还有一种高级做法。。。我不会
– https://twitter.com/heno_code/status/1590682021369884672
Problem E.
Problem F. Islands from the Sky
显然可以二分答案，更简单的做法是，对于每一条航线，去更新所有多边形的最小可行角度，最后再取最大值即可。
只需要对多边形的每个顶点做到航线的投影，然后反正切函数即可。
Problem K. Take On Meme
最后还剩两道几何题。。。Minkowski Addition + 凸包乱搞即可。
Problem D. Guardians of the Gallery
OMG，我们先要搞出多边形内部可以看见目标点的区域，是个凸多边形，然后只要求点到这个凸多边形的距离即可。
