省选模板汇总

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$

CF605E Intergalaxy Trips

题目大意

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

$n \leq 10^3$

AGC035D Add and Remove

题目大意

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

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

CF504E Misha and LCP on Tree

题目大意

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

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

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

AGC022E Median Replace

题目大意

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

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

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

AGC034E Complete Compress

题目大意

有一棵有$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]$,使得这些区间的和最大。

求这个最大值

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×