2022/04/01 做题记录

CF161D

直接换根 dp

code: /code/2022.4.1/CF161D.cpp

CF486D

对于 $a_x$ 相等的数，我们以编号排序，这样对于每一个联通块都有一个唯一的最小值，我们枚举这个值是多少，然后我们可以通过一次 dfs 找到一个极大的合法联通块（因为我们有了最小值，所以只要最大值合法就行），然后直接 dp，$dp_x = \prod (dp_{son}+1)$

code: /code/2022.4.1/CF486D.cpp

CF697D

考虑树上 dp ，一个点某个儿子被访问时间的期望实际上就是这个点被访问时间的期望加上在这个点之后，那个儿子之前被访问的点个个数的期望，可以发现这些点就是把儿子随机排序后在那个儿子之前的点及其子树，于是每个子树有 $\frac{1}{2}$ 的概率提供贡献，直接 dp 即可。

code: /code/2022.4.1/CF697D.cpp

CF708C

考虑一个点 $x$ 原来不是重心，那么它肯定有且仅有一个子树的大小超过 $\frac{n}{2}$，而我们的操作一定是从那个子树中选一个最大的，大小 $\le \frac{n}{2}$ 的子树拿出来直接接在 $x$ 上，这样一定最优（因为如果不存在这样的方案一定怎么接都不合法）。

然后直接 dp，开个 set 记录转移点方便换根。

code: /code/2022.4.1/CF708C.cpp

CF809C

可以发现如果一个 $n*n$ 的矩形满足它的每一行和每一列都是 1~n 的排列，那么我们容易求出 $2n * 2n$ 的矩形是什么样的，左下角的矩形因为对于每一个数，它的上面都有 1~n，于是这个矩形就是左上角对于每一个数 +n，右上角也是一样，而右下角因为它只会被左下角和右上的矩形影响，而这两个矩形中不可能有 1~n 的数，于是它和左上角的矩形一样，而可以发现这样的矩形也满足每一行和每一列都是 1~2n 的排列。

而 1*1 的矩形一定满足条件，于是我们可以发现任何 $2^n * 2^n$ 的矩形都满足条件。

于是我们可以快速求出 $(x,y)$ 是什么，从大到小枚举 $2^n * 2^n$ 的矩形，如果分成 4 份后在左上角或者右下角（从二进制上考虑，就是 $x,y$ 二进制这一位相同，因为最高位是 0/1 正好把这些数分成了相等的两部分），那么我们就直接把它当成左上角对应的那一个，否则我们给答案加上 $2^{n-1}$，也把它当成左上角对应的那一个。

因为 x,y,格子上的值都是从 1 开始，于是 $(x,y)$ 上的值就是 $(x-1) \ \mathrm{xor}\ (y-1)+1$

把矩形询问转化成前缀和，我们要求的就是 $\sum_{i=0}^{x-1} \sum_{j=0}^{y-1} [i\ \mathrm{xor}\ j+1\le k](i\ \mathrm{xor}\ j+1)$

我们可以把矩形分成 $log^2$ 个形如 $[x-\mathrm{lowbit}(x)),[y-\mathrm{lowbit}(y))$ 的矩形，假设 lowbit(x) >= lowbit(y)，那么可以发现 lowbit(x) 及以上的位是固定的，而后面的位可以取任何数，每个数出现了 lowbit(y) 次，因为 x 后面位可以取 $[0,lowbit(x)]$，而这些数异或上任何一种可能的 y 后边的取法也一定是一个 $[0,lowbit(x)]$ 的排列。

code: /code/2022.4.1/CF809C.cpp

BZ3217. ALOEXT

直接块状链表，每一块开个 trie 方便查询异或最大值即可。

code: /code/2022.4.1/bz3217.cpp