支配树 支配 称节点 $x$ 支配节点 $u$，当且仅当从起始点到 $u$ 的每一条路径都必须经过 $x$。根据定义，每个节点都支配它自身。 称节点 $x$ 严格支配节点 $u$，当且 $x$ 支配 $u$ 且 $x$ 不等于 $u$。 方便起见，只考虑从起始点开始能到达的节点。显然严格支配关系一定不存在环。 称节点 $u$ 的直接支配节点为 $x…

$$ \begin{align} n\overline{a}&=\sum_{i=1}^nai\ \ n^2D &=n\sum{i=1}^n(ai-\overline{a})^2\ &=n\sum{i=1}^n ai^2-2n\overline{a}\sum{i=1}^n ai+n^2\overline{a}^2\ &…

给定 $n$ 和序列 $a_1,a_2,\cdots,a_n$，$b_1,b_2,\cdots b_n$。 定义一个区间 $[l,r]$ 的权值为：对于所有满足 $p_i\in {a_i,b_i}$，$\oplus_{i=l}^r p_i$ 的序列 $p_1,p_2,\cdots p_n$ 的最大值。 求左右端点满足 $1\leq l\leq r\…

给定 $n$ 和数字串 $a_1,a_2,\cdots,a_n$，$b_1,b_2,\cdots,b_n$。 定义一次操作为：将一个等长且不相交的前缀和后缀对应位置交换。举例：${1,2,3,4,5,6}$ 交换长度为 $2$ 的前后缀变为 ${5,6,3,4,1,2}$。 可以对 $a$ 进行任意次操作，问是否能变成 $b$。多组数据。 $1\l…

给定一个 $n$ 个点 $m$ 条边的无向图。有 $q$ 个人，第 $i$ 个人要从 $s_i$ 到 $t_i$。 现在你要给无向图的每条边定向。问是否存在一种定向方法使得所有人都能够到达目的地。 $n,m,q\leq 2\times 10^5,u_i\neq v_i,s_i\neq t_i$ sol 我的做法（186ms） 可以发现，对于一个边双…

给定 $n$ 个数字 $a_1,a_2,\cdots,a_n$。 $m$ 次询问，每次询问给定 $x$，求 $\oplus_{i=1}^n (a_i+x)$ 的值。 强制在线。 $1\leq n,m\leq 2.5\times 10^5,0\leq a_i,x\lt 2^{60}$。 sol 由于每个 $a_i$ 加的都是 $x$，所以向第 $w$…

设一个由小括号和中括号组成的串 $S$ 的权值为 $\sum_{S_i\in{\texttt{'(',')'}}} A_i+\sum_{S_i\in{\texttt{'[',']'}}} B_i$。 求所有的合法的由小括号和中括号组成的长度为 $N$ 的串中最大的权值是多少。 $2\leq N\leq 10^5,2\mid N,1\leq A_i,…

给你 $N,L$ 和序列 $0=A_0<A_1<A_2<\cdots<A_n\leq A_{n+1}=L+1,0=B_0<B_1<B_2<\cdots<B_n\leq B_{n+1}=L+1$。 每次可以选择一个数 $x(1\leq x\leq N)$，使得 $A_x=A_{x-1}+1$ 或 $A_…

如果 $max(a_1,a_2,\cdots,a_m)\cdot min(a_1,a_2,\cdots,a_m)\geq a_1+a_2+\cdots+a_m$，则整数序列 $a_1,a_2,\cdots,a_m$ 被称为好的。 如果 $a$ 的每个非空子序列都是好的，则整数序列 $a_1,a_2,\cdots,a_n$ 被称为完美的。 给定两个整…

给定一个 01 串 $s$，要求你找到一个与 $s$ 长度相等的 01 串 $t$ 并满足以下条件： 对于任意的 $l,r(1\leq l\leq r\leq n)$，$s[l:r]$ 和 $t[l:r]$ 的最长不下降子序列长度相同； $t$ 中 $0$ 的数量尽可能多。 有多解输出任意一种。$|S|\leq 10^5$。 sol 这个题非常有意…