AtCoder Beginner Contest 139 题解

AC Codes

A – Tenki

B – Power Socket

C – Lower

D – ModSum

很容易构造出答案为 $\frac{N(N-1)}{2}$ 。

E – League

同一轮中可以参加比赛的人一定是一系列二元环，因此可以用一个优先队列维护比赛的轮次，当某两个人形成一组二元环时将这组边删除，然后将他们的后继节点加入优先队列，如果最后所有边都被删除就说明有解。

F – Engines

$N$ 个向量 $(x_i,y_i)$ ，要求你选择某些向量并将它们累加，假设你选择的向量是 $(x_1^\prime,y_1^\prime),\ldots,(x_k^\prime,y_k^\prime)$ ，最大化 $\sqrt{(\sum_{i=1}^kx_i^\prime)^2+(\sum_{i=1}^ky_i^\prime)^2}$ 的值。

$N\leq 100$ 。

一个naive的猜想是：如果我们要最大化向量之和，那么我们选择的向量应该大部分都处在接近同一个方向上。更进一步地猜想：所有向量在极角排序后，我们只会选择某一段连续区间中的向量。

这个猜想的证明可以参考这里。

到这里为止，我们显然已经可以 $O(N^2)$ 暴力解决本题了。当然也可以用极角排序+滑动窗口的方法优化到 $O(N\log N)$ 。