From《算法竞赛进阶指南》。

From《算法竞赛进阶指南》。

最小圆覆盖板子。

题意

在一个平面上有 $n$ 个点，求一个半径最小的圆，能覆盖所有的点。

这两天看了 Camp 2015 的构造题选讲，在这写几道题。

可持久化 Trie 树模板。

题意

Luogu

给定一个非负数列 ${a}$，有 $m$ 个操作。

操作：

1. 在序列末尾添加一个数 $x$；
2. 找到一个位置 $p$，满足 $l \leq p \leq r$，使得 $a_p \oplus a_{p+1} \oplus \dots \oplus a_n \oplus x$ 最大，输出最大值。

可持久化并查集板子。

题意

Luogu

$n$ 个集合，$m$个操作。

操作：

1. 合并 $a$, $b$ 所在集合；
2. 回到第 $k$ 次操作后的状态；
3. 询问 $a$, $b$ 是否在同一集合。

并不顺心的一场 CF。。

模拟退火板子题。 为啥这题是黑题啊

题意

Luogu

有 $n(n\le 12)$ 只奶牛，每只奶牛有 $3$ 个朋友。现在要把这 $12$ 只奶牛排成一列，使得每只奶牛与它的朋友的距离之和最小。

这题本身挺水的，$n$ 只有 $5000$，不过这题能用斜率规划 $O(n)$ 做，正好在这总结一下斜率规划。

掉分场。