====== 做题记录 ======

可能包含一些剧透？
===== 1477 C - Nezzar and Nice Beatmap =====
 [[https://codeforces.com/contest/1477/problem/C|link]] 

tag : 构造

**题目大意**：给 $n$ 个二维平面上的点，求一个排列使得 $P$ 对任意 $i$ 有 $\angle{P_iP_{i + 1}P_{i + 2}}$ 为锐角。$n \le 5000$ 。

**题解**：
每次从没有使用过的点中选择离当前点距离最远的点，作为下一个点即可。
难以想到的简单的初中几何原理。


===== 1446 F - Line Distance =====
[[https://codeforces.com/contest/1446/problem/F|link]]

tag : 几何

**题目大意**：给 $n$ 个二维平面上的点，求在这些点两两连成的所有直线中，与原点距离第 $k$ 大的。$ n \le 10 ^ 5$

**题解**：在圆外两点连线与圆相交时，设他们的切线在圆上弧度分别为 $[l_1, r_1], [l_2, r_2]$，那么当这两个区间相交（不包括包含）时，直线与圆相离。
可以画图感受一下

===== 1446 D - Frequency Problem =====
[[https://codeforces.com/contest/1446/problem/D1|link]]

**题目大意**：给一个长度为 $n$ 的序列 $a$ ，求出最长的 **subarray** ，使得 subarray 中的众数不唯一。$n \le 2 \times 10 ^5, a_i \in [1, A]$。

Subtask 1 : $A \le 100$ ；Subtask 2 : $A \le n$

**题解**：设整个序列的众数为 $f$，那么 $f$ 也一定是所求 subarray 中的众数之一。

Subtask 1： $O(n)$ 枚举另一个众数；对所有前缀，维护 $cnt_f - cnt_i$。

Subtask 2： 分块。出现次数大于 $k$ 用上面的暴力求。剩下的数只需要在出现位置前后 $T$ 个 $f$ 的位置处维护即可。复杂度 $O(nk + n ^ 2 / k)$。
===== 1421 E - Swedish Heroes =====
[[https://codeforces.com/contest/1421/problem/E|link]]

**题目大意**：给一个长度为 $n$ 的序列 $a$ ，每次可以将相邻的两个数 $a_i, a_{i+1}$ 删除，将 $-(a_i + a_{i + 1})$ 放入原来的位置。求在 $n - 1$ 操作后剩下的数最大值。 $n \le 2 \times 10 ^ 5$。

**题解**：考虑每一位对最终答案的贡献，$a_i$ 最终可能变为 $+a_i$ 或 $-a_i$。牛逼结论： $(n + 负号个数) \mod 3 == 1$，并且至少存在两个连续的符号相同的 $a_i$。然后就能 dp 了。