0. 写在前面

这里的内容是为即将到来的省选做准备，主要参考来源是OI-wiki、lydrainbowcat的《算法竞赛进阶指南》和hzwer的《OI省选算法汇总》，在此鸣谢

题目大意

你有$3$个数组，分别是$\texttt{r, g, b}$，长度分别是$n_r, n_b, n_g$

你需要在这三个数组中选择一个数，设你选择的三个数为$x, y, z$，则你要使$(x-y)^2+(y-z)^2+(z-x)^2$最小

多组数据，$1 \leq n_r, n_b, n_g \leq 10^5$，值域$1 \leq r_i, b_i, g_i \leq 10^9$

题目大意

给定一颗有根树，根为 $1$ ，有以下两种操作：

1. 标记操作：对某个结点打上标记。（在最开始，只有结点 $1$ 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）

2. 询问操作：询问某个结点最近的一个打了标记的祖先。（这个结点本身也算自己的祖先）

$1 \leq n, q \leq 10^5 $

题目大意

有一棵$n$个节点的树，点有点权，对于每个节点，你要求出离这个节点距离$k$以内的节点的点权和

$1 \leq n \leq 10^5, 1 \leq k \leq 20$

题目大意

有一个有$n$个点的有向完全图，每条边每天有一个开放几率$p[i][j]$，给定$p$，你需要求出从$1$到$n$的期望天数

$n \leq 10^3$

题目大意

有一个长度为$n$的序列${a_i}$，每次可以选择连续的$3$个数，把中间那个数加到左右两个数上后删除中间那个数。

求最后剩下的两个数的最小值。 $n \leq 18$

题目大意

给你一棵有$n$个节点的树，每个节点上有一个字符$c$。

有$m$次询问，每次询问$a\sim b$路径上的字符串和$c \sim d$路径上的字符串的最长公共前缀$\texttt{(LCP)}$

$n \leq 3 \times 10^5，m \leq 10^6$

题目大意

你有一个长度为$n$的串$\texttt{S}$，其中有一些位置上的字符是?，其他的字符则是$0/1$之间的一种

每次可以进行一步操作：选择$3$个连续的字符，并把它们用它们的中位数替换

求有多少种把?替换成$0/1$的方案使得在进行$\frac{n-1}{2}$次操作后剩下的字符为$1$？

题目大意

有一棵有$n$个节点的树，每个节点上有$0/1$枚棋子，每次可以选择两个棋子并移动到它们的路径上的相邻节点（满足路径长度至少为$2$），求把所有棋子移到同一个节点的最小花费（无解输出$-1$）。

$n \leq 2 \times 10 ^ 3$

题目大意

你有一个序列${a_i}$，你要找出$k$个不相同的区间$[l_i,r_i]$，满足$\forall \; i, (r_i-l_i+1) \in [L, R]$，使得这些区间的和最大。

求这个最大值