格雷码

模拟即可。需要注意的是要开 unsigned long long

代码

括号树

先考虑一条链的情况,即给出一个括号序列,求出每个前缀的所有子段中有多少个合法括号序列。

假设我们在计算 $[1,i]$ 的答案,那么它显然等于 $[1,i-1]$ 的答案加上强制选 $i$ 的答案。

维护一个栈表示所有未被匹配的左括号,再求出一个 $len_i$ 表示存在某个位置 $p$,满足 $[p,i]$ 能够拆成 $len_i$ 段,且每段都是合法括号序列,在此基础上最大的 $len_i$。

假设 $i$ 是右括号,记 $pre_i$ 表示与 $i$ 匹配的左括号的位置,显然有 $len_i=len_{pre_i-1}+1$。然后强制选 $i$ 的答案就是 $len_i$。

然后把这个东西搬到树上即可,具体的一些细节可以看代码。

代码

树上的数

咕咕咕

Emiya 家今天的饭

首先可以把烹饪方法看做行,主要食材看做列。

考虑容斥掉第三个限制。注意到不满足第三个限制的列至多只有一个,因此我们仅需要计算出无第三个限制时的方案数以及某一列超过 $\left\lfloor\frac{k}{2}\right\rfloor$ 时的方案数。

首先计算第一部分(无第三个限制时的方案数)。设 $f_{i,j}$ 表示前 $i$ 行选了 $j$ 个的方案数,$sum_i$ 表示第 $i$ 行的和,容易得到

$$ f_{i,j}=f_{i-1,j}+sum_i\times f_{i-1,j-1} $$

然后计算第二部分。假设钦定了第 $c$ 列不满足限制。设 $g_{i,j}$ 表示前 $i$ 行,第 $c$ 列选的数比其它列选的数多了 $j$ 的方案数,容易得到

$$ g_{i,j}=g_{i-1,j}+a_{i,c}\times g_{i-1,j-1}+(sum_i-a_{i,c})\times g_{i-1,j+1} $$

然后算答案就很简单了。

代码

划分

容易发现段数越多答案会越小,证明略。

设 $sum_i$ 为前缀和,$pre_i$ 表示最大的满足 $sum_i-sum_k\geq sum_k-sum_{pre_k}$ 的 $k$。

那么每个 $i$ 都会从 $pre_i$ 转移过来。

考虑如何快速求出 $pre_i$。我们把这个式子移一下项

$$ sum_i\geq 2sum_k-sum_{pre_k} $$

用单调队列维护即可。

实现时开高精数组可能会爆空间,事实上直接最后利用 $pre$ 求出方案并算出答案即可。当然也可以直接 __int128

代码

树的重心

考虑到一个事实:如果 $u$ 不是重心,则重心在 $u$ 的重儿子所在的子树中。

那么就有一种找重心的方法:不断跳重儿子直到不可能为重心,此时最后一个可能为重心的点和它的父亲都可能是重心,检查一下即可。

这样子是 $\mathcal{O}(n)$ 的,使用倍增即可优化至 $\mathcal{O}(\log n)$。

现在考虑如何求出删去一条边后得到的两棵树的重心。假设删去了 $(u,v)$ 且 $u$ 是 $v$ 的父亲。

考虑一下我们需要什么东西才能求出重心。我们需要一个重儿子的倍增数组,和一个记录子树大小的数组。

那么 $v$ 子树中这些东西和原树中相同,可以直接求;而 $u$ 子树中的这些东西用换根法求出即可。

代码


版权属于:小宇宙

转载时须注明出处及本声明

最后修改:2019 年 12 月 03 日 09 : 32 PM