可能包含一些剧透？

link

tag : 构造

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

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

link

tag : 几何

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

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

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)$。

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 了。