BAPC 17
Contest Info
date: 2018.08.06 12:00-17:00
Solutions
A. Amsterdam Distance
签到题
B. Bearly Made It
题目大意：给你平面上 \(n\) 个圆和两个在圆内的点，问你这两个点在圆内走的最短距离。
题解：显然只会走圆的交点或切点，如果两个点的连线段完全在圆内，那么在它们间连一条长度为它们间的欧氏距离的边，跑最短路即可。
判断线段是否在圆内时，可以将它所在直线与所有圆的交点求出，进入一个圆记为 \(+1\)，出一个圆记为 \(-1\)，将这些点排序后求一个前缀和，判断该线段的前缀和是否恒大于 \(1\) 即可。（W comment: 考虑端点的时候多注意一下。）
时间复杂度 \(\mathcal{O}(n^{5}\log n)\)。
C. Collatz Conjecture
题目大意：求一个数列所有区间的 gcd 的不同的值个数。
题解：从左往右扫，记录前一个位置的所有后缀的 gcd，然后移动的时候把当前的值往里面插入即可。\(\mathcal{O}(n\log^2 A)\)，这里的 \(\log\) 很小。
D. Detour
签到题
E. Easter Eggs
题目大意：二维平面上有 \(B\le500\) 个蓝点和 \(R\le500\) 个红点，现在要从中选出 \(N\le B + R\) 个点，最大化红点与蓝点之间的最小距离。
题解：二分之后用二分图最大独立集判断是否可行。
F. Falling Apart
签到题
G. Going Dutch
题目大意：在 \(m\le20\) 个人之间发生了 \(n\) 次交易，第 \(i\) 次交易为 \(a_i\) 借给 \(b_i\) 金额为 \(p_i\) 的一笔钱。所有交易结束后，他们打算以一对一转账的方式清算所有债务，假设每个人有无限的现金，单笔转账金额不限，求最少转账次数。
题解：记第 \(i\) 个人的债务为 \(a_i\)，若集合 \(S\) 满足 \(\sum_{i\in S} a_i = 0\)，那么可以通过 \(|S|-1\) 次转账清算债务（第 \(i\) 个人与第 \(i+1\) 个人发生一次转账使得第 \(i\) 个人的债务清零）。
令 \(\text{dp}[s]\) 为集合 \(s\) 最多划分为多少个合法集合，则 \(\displaystyle\text{dp}[s] = \max_{i\in s} \left(\text{dp}\left[s\backslash \{i\}\right] + \left[\sum_{i\in s} a_i = 0\right]\right)\)。 时间复杂度\(\mathcal{O}(m\cdot 2^m)\)。
H. Hoarse Horses
题目大意：给你平面上的 \(n\) 条线段，问你这些线段围成的具有有限、正的面积的区域有多少。保证没有三线共点的情况。
题解：使用欧拉公式容易证明，答案即为 \(\displaystyle \text{连通块数量} - n + \text{交点个数}\)（重合算做有一个交点）。由于坐标范围达到了 \(10^{9}\)，而 double 的精度只有 \(15\) 位左右，因此需要使用整型来严格判断是否相交。
I. Irrational Division
题目大意：一个 \(p\times q\) 的网格，左上角是黑色，其余格子依次黑白相间。两人玩游戏，先手每次可以拿走左起若干列，后手每次可以拿走底部若干行。每个人的得分是黑格子数减去白格子数。最大化先手得分减后手得分。
题解：答案只可能为 \(0,1,2\)。分析一下 small case 可以发现有规律：
- 如果 \(p\) 偶，那么答案为 \(0\)
- 如果 \(p,q\) 均为奇数，那么答案为 \(1\)
- 如果 \(p\) 奇数，\(q\) 偶数，那么 \(p<q\) 时答案为 \(2\)；\(p>q\) 时答案为 \(0\)
J. Jumping Choreography
题目大意：在无限大的一维坐标轴上有 \(n\le5000\) 只青蛙（坐标范围 \([0,10^6]\)），每一只青蛙都要跳跃到目标坐标 \(0\le t\le10^6\) 并停止，并且它第 \(i\) 次跳跃的长度必须等于 \(i\) ，求所有青蛙跳跃的最小总步数（不要求同时到达 \(t\)）。有 \(m\le10^6\) 次询问，每次询问添加或者删去一只青蛙（不超过 \(5000\) 次)，或者修改目标点，输出修改后的答案。
题解：记 \(f_i\) 为跳到离起点距离为 \(i\) 的最小步数，对于奇数和偶数 \(i\) 单独考虑，则为两个单调增的函数，且对于 \(i\le10^6\) ，打表发现一共只有 \(1416\) 个不同的取值。
预处理出值发生变化的点与变化后的值，用两个树状数组分别维护奇数和偶数的答案，增加或者删除时做 \(1416\) 次区间修改，询问直接去树状数组中询问即可。
时间复杂度 \(\mathcal{O}(1416\cdot n\log{10^6} + m\log{10^6})\)。
zhongzihao’s comment
我们可以归纳地证明，跳 \(f_i\) 步能够跳到的位置是所有与 \(\frac{f_i(f_i+1)}{2}\) 奇偶性相同，且在 \([-\frac{f_i(f_i+1)}{2},\frac{f_i(f_i+1)}{2}]\) 间的整数，这样 \(f_{i}\) 就很容易求出了。
K. King of the Waves
题目大意：\(n\) 个人打擂台，知道任意两两的胜负关系，要求你给出一个顺序，使得编号为 \(1\) 的人最后获胜。
题解：从 \(1\) 开始 dfs，如果能访问到每个人，那么有解。回溯的时候依次输出即为一个可行方案。
L. Lemonade Trade
题目大意：一开始有 \(1\) 单位的 pink 饮料，依次经过 \(n\) 个人，每个人可以把无限的 \(w_i\) 颜色的饮料按照 \(R\) 的比例换成 \(o_i\) 颜色。问最后最多能有多少 blue 饮料，如果 blue 饮料大于 \(10\)，取 \(10\)。
题解：如果要换，那么一定是换掉所有的量。那么最后的解是一个子序列。我们维护每个时刻，每个颜色的最大量即可。用 log 减少精度损失。
M. Manhattan Mornings
签到题
Dirt Replay
C: -2 Z 想了一个 log 比较大的 log^2 算法，D 实现的时候返回值没用 ll；TLE
M: -1 把排序放到了归约情况之前，应该放在之后
