2015-2016 Northeastern European Regional Contest (NEERC 2015)

主要在做图论专题的相关练习，把板子和不熟悉的知识点都过了一遍。

1. 莫比乌斯反演
2. 环空间
3. 连通分量
4. 差分约束系统

题目链接

题意：给 $n \leq 4000$ 个点，求面积最大的凸四边形。

题解：显然可以枚举对角线上的两个点，现在要找到距离对角线最远的两侧的点。先固定一个点 $A$，按相对 $A$ 的极角序枚举对角线的每一个点 $B_i$。

考虑所有点构成的一个凸包。显然，最远的点只能在凸包上取到。假设凸包上一点 $P$，随着 $i$ 的增大，$P$ 到 $AB_i$ 的距离是先增大后减小的（可以模拟一下）。同时，随着 $AB_i$ 的转动，最远的点应该是和旋转卡壳一样在凸包上单调移动的（这个过程和旋转卡壳很像）。因此维护好这个凸包，在上面单调指针移动即可维护最远点。

题目链接

链接

其中 E 题的思路与 CF1244F Chips 几乎一致，是这一道题的二维版。

主要进行了字符串、数论和图论的练习。

2020.5.10 扩欧 原根 BSGS N 次剩余

2020.5.14 连通分量

2020.5.15 LGV 引理

字符串将作为下周主要内容，故略。

题目链接

题意：

题解：