Contest Info

date 2017.08.05 12:00-17:15

practice link

Solutions

A. Area

题目大意：求一个球的两个球冠并的面积占球表面积之比。

题解：先求一下球冠的表面积。设球冠的高为 \(h\) ，球的半径为 \(R\) ：

\[ \begin{aligned}\\ S&=\int_{\theta_{0}}^{\frac{\pi}{2}}2\pi R\cos\theta\cdot R\mathbb{d}\theta\\ &=2\pi R^{2}(1 - \sin\theta_{0})\\ &=2\pi Rh\\ \end{aligned}\\ \]

求两个球冠的面积并显然只要把两个球冠的面积加起来再减去它们交的面积即可。我们仿照求平面两圆交的面积的方法来求球冠交的面积。

若两个球冠的半径之和 \(r_{1}+r_{2}\) 小于两球冠中心的距离 \(d\)，则答案为两球冠面积之和。

若它们半径之差的绝对值大于球冠中心的距离，则答案为两球冠面积中较大的那个。

否则这两个球冠相交，相交部分的面积为两球冠中心与两个交点形成的两个扇形的面积之和减去两球冠中心与两个交点形成的两个对称的球面三角形的面积之和。由于我们已经知道了三角形的三条边长，为方便设 \(a=r_{1},b=r_{2},c=d\)。我们可以通过余弦定理 \(\displaystyle \cos C=\frac{\cos c - \cos a \cos b}{\sin a \sin b}\) 来求出三个角的大小。这两个三角形的面积和即为 \(2(A+B+C-\pi)R^{2}\) ，而显然两个扇形的面积和为 \(2ARh_{2}+2BRh_{1}\) ，这样就解决了这个问题。

本题用到了大量的三角函数和反三角函数，精度很低，需要使用 long double 才能通过本题。

B. Parade Show

跟这题一样 POJ 3167

C. Count The Pairs

题目大意：给出 \(n\) 个点和 \(m\) 条边的无向图，保证边权两两不同。 \(p\) 次询问，每次询问给出一个非负整数 \(t\) ，问有多少点对 \((u,v)\) 满足从 \(u\) 到 \(v\) 的最小瓶颈路中的瓶颈边不小于 \(t\)。

题解：无向图的最小生成树一定也是它的最小瓶颈生成树。用 Kruskal 算法求最小生成树，当加入一条新的边 \((u,v)\) 的时候，以这条边为瓶颈边的点对共有 \(siz(u) \times siz(v) \times 2\) 对，其中 \(siz(x)\) 表示 \(x\) 所在的连通块的大小，用并查集顺便维护。这样当我们求出最小生成树的同时，也计算出了每个边权作为最小瓶颈路的时候的贡献，再搞一个后缀和，然后询问的时候去二分找到刚好不小于 \(t\) 的位置输出答案。时间复杂度为 \(\mathcal{O}(m \log{m} + p \log{n})\)。

D. Divide Groups

题目大意：给定一个有向图，问你是否能将点集分成两部分，且每部分内部的点两两之间有双向边连接。

题解：枚举所有的点对，将没有双向边的点对各自加入到对立集合中去，如果一直到枚举结束没有产生矛盾，那么就是可行的。用并查集维护即可。

E. Polygon

题目大意：给你一个简单多边形（不一定凸）和一段 \([l, r]\) 上的抛物线，求抛物线在多边形内的长度。

题解：zzh 和计算几何有仇系列。先求一下抛物线的长度公式（也可以直接辛普森积分计算），免得连积分是什么都不知道了： \[ \begin{aligned}\\ &\int\sqrt{(2ax+b)^{2}+1}\mathbb{d}x\\ =&\frac{1}{2a}\int\sqrt{x^{2}+1}\mathbb{d}x\\ 记 I& =\int\sqrt{x^{2}+1}\mathbb{d}x，有\\ I =&x\sqrt{x^{2}+1}-\int x\mathbb{d}\sqrt{x^{2}+1}\\ =&x\sqrt{x^{2}+1}-\int(\sqrt{x^{2}+1}-\frac{1}{\sqrt{x^{2}+1}})\mathbb{d}x\\ I=&\frac{1}{2}x\sqrt{x^{2}+1}+\frac{1}{2}\int\frac{\mathbb{d}x}{\sqrt{x^{2}+1}}\\ =&\frac{1}{2}x\sqrt{x^{2}+1}+\frac{1}{2}\int\frac{\mathbb{d}\tan\theta}{\sqrt{\tan^{2}\theta+1}}\\ =&\frac{1}{2}x\sqrt{x^{2}+1}+\frac{1}{2}\int \sec\theta \mathbb{d}\theta\\ =&\frac{1}{2}x\sqrt{x^{2}+1}+\frac{1}{4}(\ln|\sin\theta+1|-\ln|\sin\theta-1|)+C\\ =&\frac{1}{2}x\sqrt{x^{2}+1}+\frac{1}{4}\ln\left| \frac{\tan\theta\sqrt{\frac{1}{\tan^{2}\theta+1}}+1}{\tan\theta\sqrt{\frac{1}{\tan^{2}\theta+1}}-1} \right|+C\\ =&\frac{1}{2}x\sqrt{x^{2}+1}+\frac{1}{2}\ln(x+\sqrt{x^{2}+1})+C\\ \int_c^{d}\sqrt{(2ax+b)^{2}+1}\mathbb{d}x=&\frac{1}{4a} ( (2ad+b)\sqrt{(2ad+b)^{2}+1}+\ln \left( 2ad+b+\sqrt{(2ad+b)^{2}+1} \right)\\ &-(2ac+b)\sqrt{(2ac+b)^{2}+1}-\ln \left( 2ac+b+\sqrt{(2ac+b)^{2}+1} \right) ) \end{aligned}\\ \]

接下来给出两种解法：

法一：分类讨论。我们求出抛物线和多边形的所有交点，根据相交的方式判断抛物线在多边形中的位置，并计算所有在多边形中的部分的长度和。

• 交点不是多边形的顶点
  • 若相切，不改变内外状态
  • 否则改变内外状态
• 交点是多边形的顶点
  • 若抛物线与这个顶点的两条边都不相切，则判断两条边是否在抛物线过该点切线的两侧，若是，则改变内外状态，否则不改变
  • 若抛物线与其中一条边相切，则判断抛物线和不相切的边是否在相切的边的同一侧，若是，则改变内外状态，否则不改变

此法精度比较差（也可能是我的代码写得太丑），需要使用 long double 才能通过本题。

法二：解法来源于这个博客

方法是使用有向线段来计算长度。对于每条线段求出抛物线和它所在直线的交点，若超过了这条线段的两个端点或者超出了 \([l,r]\) ，就把交点缩小到它们的范围内。之后规定一个正方向，根据两个端点的横坐标的大小判断应该加上还是减去这个长度。感觉思想类似于求多边形的面积。由于实现简单，这个方法的精度也很容易控制。

F. Parade Show

题目大意：给定一个 \(3\times 3\) 的网格，两人在这个网格上进行游戏。两人交替进行操作，每次选择一条没有被覆盖的边，将其覆盖，并收益覆盖掉这条边形成的正方形个数（只考虑 \(1\times 1\) 的正方形）。现在给定一个残局，问先后手谁胜。

题解：状压 dp。设 dp[s] 表示当前边覆盖的局面为 \(s\) 时的 \(\mathrm{max} \{now - opp\}\)，其中 \(now\) 表示将要进行操作的人的收益，\(opp\) 表示他的对手的收益。

那么状态转移方程便是：

\[ dp[s] = \mathrm{max}\{ c_i - dp[s\cup \{i \}]\} \]

其中 \(c_i\) 表示当前局面覆盖 \(i\) 这条边的收益。

那么每次询问的时候，先计算出双方在残局中的收益，再去记忆化搜索相应的状态，就可以知道先后手的胜负了。很容易看出得分一共是 \(9\) 分，所以不会有平局。转移状态的时候可以用 __builtin_ctz() 优化常数，事先预处理打表也可以很快的算出 \(c_i\)。

G. Spacecraft Monitoring

unsolved

H. Heroes of Might and Magic

unsolved

I. Install Air Conditioning

题目大意：平面上给定 \(n\) 个整点。\(1\) 号点是电站，其余 \(n-1\) 个点是宿舍。两点之间的距离是欧几里德距离。求断掉恰好一条宿舍之间的边的最小生成树的最大值。

题解：因为是稠密图所以用 Prim 先求出一个最小生成树。然后我们枚举树上的可断边，如果我们能事先求出断掉某条边之后的两个点集之间的最小距离，那么这题就解决了。

法一：我们用 \(\mathcal{O}(n^2)\) 的 dp 来求出这个东西。定义 dp[u][v] 表示断掉 \((u,v)\) 这条边之后，两个点集的最小距离。我们枚举最小生成树中的每一个点，将它提起来作为根，设为 \(root\)。我们在 dp 的时候，定义 f[u] 表示以 \(u\) 为根的子树中的点，到 \(root\) 的距离的最小值。很容易写出 \(\mathcal{O}(n)\) 的 dp 转移。我们每次枚举并求出 f 之后，再用 f 去更新 dp 即可。

法二：（tls队的做法）对 \(\mathcal{O}(n^2)\)条非树边排序。依次枚举每条边，用它更新这条边的两个端点在树上的路径中的每条边的 dp 值。然后用一个并查集缩边。

J. Tree

题目大意：一棵点上带权的树。每次询问 \(x, y\) 的路径上选择一个点与 \(z\) 异或的最大值。

题解：每个点维护一个到根的可持久化 trie，把询问拆成两条链。

K. Walk Through Squares

题目大意：给出两个只由 R 和 D 组成的字符串，问有多少个串满足：

• 只由 R 和 D 组成，且 R 有 \(n\) 个，D 有 \(m\) 个
• 包含两个给出的串作为子串

题解：跟这题是一样的，只是修改一下 dp 状态把 R 和 D 的个数记录下来就行了。

Replay and Summary

Replay

一开始 W 看到 J 名字叫 tree，果断接锅去看题，看完之后发现果然是一个 sb 题，随手写了一个树上的可持久化 trie 就 MLE 了。将动态开空间去掉之后，因为数组开小又 TLE 了一次。为本场比赛罚时爆炸奠定了基础。

D 看了 C 题觉得是个最小瓶颈生成树，拿过键盘就写过了。成功 a 掉本场比赛唯一一道没有罚时的题。接下来 W 听 Z 讲了 D 的题意之后，表示很嫌弃 Z 的写法，同时也想放 Z 去做那几道计算几何题，于是就开始写。写了三种算法判断了各种情况还是 wa 了，Z 跟 D 讨论了一下他们的解法觉得没问题，也过来 a 掉了。a 掉之前交错代码又 wa 了一次（交的 W 的错误代码）。

D 发现 K 题是之前字符串专题中 A 题的弱化版，于是 W 接锅修改了一下 dp 函数。因为忘记取模 wa 了一次，也过掉了。

D 和 W 趁 Z 在刚计算几何，发现 B 似乎就是一个 kmp。瞎转换了一下口头验证感觉没问题，写了之后因为没有判断 m = 1 的特殊情况又 wa 了一次。

D 和 W 继续趁着 Z 在刚计算几何，口胡了一下 F 直接状压 dp 加上记忆化搜索。感性理解了一下觉得可用的状态很少，而且询问也不多，而且 W 觉得正好可以用到才学的 __builtin_ctz() 来优化常数，然后就写了。然后因为打表一个数字写错了，又 wa 了一次。更让人感动的是，W 写 F 的打表的时候，还叫上了 Z 在旁帮忙检查。

D 和 W 仍然趁着 Z 在刚计算几何，开始想 I 题。问题一直在如何求树上被一条树边分开的两部分经过非树边的最小边权。在 dp 上想了很久，突然发现 n 只有 1000。于是直接先枚举每个点作为最小边权的一个端点即可。W 因为没怎么想清楚，也没好好跟 D 讨论，导致 D 很早就怀疑有问题的一个地方被忽略掉了，也 wa 了很多次。

看了看总榜没有跌到 7 题最后，还是很感动。（最后 Z 也没做出计算几何）。

coldwater

这场比赛贡献还是不错，但是没有管住大家胡来的双手，导致罚时爆炸，有点亏。因为 Z 一直在刚这场的两道计算几何题，导致只有我和 D 在想题。两人一直在讨论，也过掉了很多题。但是做 I 题的时候有点慌了，导致还没有完全讨论清楚就开始写，中途也没有能及时停下来听取 D 的建议，导致这题 wa 了好几次。感觉自己 1a 题目的能力还是有点差。

ShinriiTin

新的机房没有电脑，本来准备只是看题的话就懒得背电脑过来了，结果就尴尬了。一来先用手机看题，看了 K 和 C，一开始以为 K 有点读错了题意，C 想了一下想到了做法，就去写了一发 a 了，期间看到 W 交 J 的时候动态开点提醒了一下。然后 K 又读了一遍题看了下样例读对了题意，发现和字符串专场的一道题很像，就和 W 说了让他去写，因为当时是他做的。然后 W 和 Z 让我读 D，读完之后我和 Z 的想法是一样的，我觉得应该没有问题，然后 Z 发现他上一次提交粘错代码了，重新交了一下就 a 了。然后读了 B ，感觉是 kmp ，给 W 说了一下，他去推了一下就去写了，因为没有处理 m=1 的情况 wa 了一次，改正后也 a 了。在 W 写题的时候我想了下 F，感觉就是状压记忆化搜索一下，但是要枚举下一次选的边，可能时间复杂度有点问题。等 W 写完我跟他说了 F，他刚好昨天有看到快速取出二进制数中 0 的方法，就去写了，因为打表打错了一个位置 wa 了一次，检查改正之后也 a 了。然后我和 W 一起想 I，我感觉很僵硬，一直在想 Delaunay 三角剖分。W 给我讲了一下他的想法，我感觉没问题，就看着他写。W 写的时候我感觉他有一个问题，但是 W 坚持没有问题，就一直写完了。然后 wa 了好几次，期间我给出了一种情况的数据让他的程序出错了，然后改正后还是 wa。之后就很绝望的改改交交，然后突然就 a 了。之后又对比了一下前后提交的代码，发现的确是我一开始发现会存在的那个问题。这一场我除了做了一道 C 之外，就一直在读题口胡辅助，可能是因为昨天写由乃题浪费了时间有点害怕。这一场的罚时非常不值得，好多次错误提交都是可以避免的，以后的比赛中要注意。

zhongzihao

计算几何这种东西真是让人绝望。。于是我已经摸了两场鱼了。总之今天要好好补这种恶心人的题（堆了三道了）。其它没什么好说的，求下次的计算几何能 A 。