$\text{Splay}$ 是一种二叉查找树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链。

爬山算法和模拟退火都是基于随机化的算法，常用于求函数极值。当一个问题的方案数量极大甚至无穷时，我们一般考虑这两种算法。爬山算法和模拟退火适用于在一个大的搜寻空间内找寻问题的最优解，但是爬山算法一般只用于单峰函数。

莫比乌斯反演是数论中的重要内容。对于一些函数，如果很难直接求出它的值，而容易求出其倍数和或约数和，那么可以通过莫比乌斯反演求得原函数的值。

题目列表

1. 「A 酱的体育课」
2. 「B 酱的无向图」
3. 「C 酱的商店」

题目列表

1. 「Prefix Sum」
2. 「Bead」
3. 「Train」
4. 「监视 G 房」

Description

题目链接：Codeforces 1027C

给出 $n$ 条线段，在其中选择 $4$ 条线段组成一个矩形，记 $P$ 为围成的矩形的周长，$S$ 为围成的矩形的面积，求使得 $\frac{P^2}{S}$ 最小的 $4$ 条线段。

本题 $T$ 组数据。

数据范围：$1\le T\le 10^6$，$4\le\sum n\le 10^6$，$1\le a_i\le 10^4$

Description

题目链接：Codeforces 1027D

有 $n$ 间屋子和 $1$ 只老鼠，老鼠会从第 $i$ 间房子跑到 $a_i$ 间房子。在每间房子放捕鼠夹都有代价 $c_i$，而老鼠的初始位置可能是任何一个房间，为了保证抓到老鼠（无论老鼠在哪个房间，总有一种路径会经过有捕鼠夹的房子），你需要在若干房间放上捕鼠夹，求最小代价和。

数据范围：$1\le a_i\le n\le 2\cdot 10^5$，$1\le c_i\le 10^4$

Description

题目链接：BZOJ 4753

有 $N$ 名候选人，从 $1$ 到 $N$ 编号，队长编号为 $0$，每个候选人都由一位编号比他小的候选人推荐（如果为 $0$ 则表示是队长推荐的）。队长希望招募 $K$ 个人，但是他需要保证：如果招募了 $x$，那么他的推荐人也要招募（队长总是在团队里的）。每个人都有代价 $C_i$ 和价值 $W_i$ 两个值，招募可以获得的价值为 $\frac{\sum W_i}{\sum C_i}$，你需要最大化这个值，答案保留 $3$ 位小数。

数据范围：$1\le K\le N\le 2500$，$1\le C_i,W_i\le 10^4$

Description

题目链接：BZOJ 4033

有一棵 $N$ 个节点的树（有边权），选择 $K$ 个点染成黑色，其他点染成白色。最后得到的收益为“黑点两两之间的距离和，白点两两之间的距离和”之和，要求最大化收益。

数据范围：$0\le K\le N\le 2000$

Description

题目链接：AGC 005D

给出 $n$ 和 $k$，求有多少个长度为 $n$ 的排列 $a$ 使得对于任意的 $1\le i\le n$，都满足 $|a_i-i|\neq k$。

数据范围：$2\le n\le 2000$，$1\le k<n$