ZJOI2022 做题记录
whiteqwq
·
·
个人记录
这一场质量挺高的。
更好的阅读体验
D1T1 树
枚举第一棵树的叶子集合，第二棵树的叶子集合为恰好，容斥成钦定：（f_1(S) 为第一棵树叶子集合为 S 的方案数，f_2(S) 为第二棵树非叶子集合为 S 的方案数）
\sum_Sf_1(S)\sum_{T}(-1)^{|S|-|T|}f_2(T)=\sum_S(-1)^{|S|}f_1(S)\sum_{T}(-1)^{|T|}f_2(T)
考虑对这个式子直接 dp，令 f_{k,i,j} 表示 dp 到了编号 k 的结点，目前前面钦定了 i 个非叶子结点，后面提前钦定了 j 个非叶子节点的容斥系数和。
分讨列出转移方程，大概就是枚举结点分配给哪棵树，然后再确定另一棵树是否钦定它来容斥（很神秘）：
- 这个结点分配为第一棵树的叶子，第二棵树钦定：f_{k+1,x,y}\leftarrow -xyf_{k,x,y}；
- 这个结点分配为第一棵树的叶子，第二棵树不钦定：f_{k+1,x,y}\leftarrow xyf_{k,x,y+1}；
- 这个结点分配为第二棵树的叶子，第一棵树钦定：f_{k+1,x,y}\leftarrow -xyf_{k,x,y}；
- 这个结点分配为第二棵树的叶子，第一棵树不钦定：f_{k+1,x+1,y}\leftarrow xyf_{k,x,y}。
复杂度 O(n^3)。AC
D1T2 众数
显然答案的形态就是 aaabbbaaa，考虑对颜色出现次数根号分治：
- a/b 存在一个是大颜色：枚举每一个大颜色，扫一遍序列，对每种颜色维护一个极长的 aaabbb 段以及一个 bbbaaa 段即可。
- a/b 均为小颜色：枚举处于外面的颜色，那么问题转化为 O(n\sqrt n) 次区间众数。但此时众数大小不超过根号，我们将询问有序地挂在右端点，枚举众数出现次数，移动右端点并维护符合条件最靠后的左端点，弹符合要求的询问就好了。
这样就做到了 O(n\sqrt n)。AC
D1T3 简单题
可以证明原图是一个杏仁树：对于每个环上只会有最多一对点能通过环外的路径互相到达，即每个点双都是杏仁。
我们对每个杏仁处理出 (c,s) 表示方案数，权值和。缩杏仁（有交点、连边的杏仁都要连边）之后，在树上随便合并一下这些 pair 就好了。
那么问题就是处理出一个点双的方案数与权值和了。也就是说，我们要计算一个杏仁上两个点之间的路径数及它们权值之和。
设杏仁链数为 w，链的权值和为 t，那么有：
- 若两个点在杏仁的一条链上，(c,s)=(w,t-dis(A,B)+dis(x,y)+(w-1)(dis(A,x)+dis(y,B)))=(w,t+(w-2)(dis(A,x)+dis(y,B)))。（A,B 为杏仁的两端）
- 若两个点不在杏仁的一条链上，类似地可以得到 (c,s)=(2(w-1),2t+(w-3)(dis(A,x,B)+dis(A,y,B)))。
然后就做完了，复杂度 O(n\log n)。
D2T1 面条
将最后答案除以 2^k，那么我们第二个操作就不需要要除二了。
我们手玩一下操作过程：
abcdefgh\cdots z\rightarrow aabbccdd\cdots zz\rightarrow\cdots (a\times 2^w)(b\times 2^w)\cdots(z\times 2^w)\rightarrow (a\times 2^{t+1})(b\times 2^{t+1})\cdots(z\times 2^t)
（其中一个字母在不同阶段不代表相同数字）
也就是说，令 t 为 n 最低非零位，那么我们应用 t+1 次操作后，会变成很多个长度为 2^{t+1} 的相同段，最后接一个长度为 2^t 的相同段。
显然这个过程的操作与询问都可以在 O(n\log n) 内暴力模拟。
将长度为 2^t 的相同段缩成一个字母，令新的序列为 c_1,c_2\cdots,c_m。考察接下来的操作造成的影响：
c_1,c_2,\cdots,c_m\rightarrow c_1+c_m,c_1+c_{m-1},c_2+c_{m-1},c_2+c_{m-2},\cdots
令差分数组为 d，那么操作就为：
d_1,d_2,\cdots,d_{m-1}\rightarrow -d_{m-1},d_1,-d_{m-2},\cdots
那么，一次操作就是 d_1,d_2,\cdots d_{m-1},-d_1,-d_2,\cdots,-d_{m-1} 的一次置换，令这个置换为 g，我们询问的答案就是：
C+\sum_{i=1}^{m-1}[g^k(i)<x]d_i=C+\sum_{i=1}^{x-1}d_{g^{-k}(i)}
将大小相同的置换环的答案加到一起，每次询问只需要枚举 $O(\sqrt n)$ 个置换环将答案加起来即可，复杂度 $O(n\log n+q\sqrt n)$，不能通过。
继续挖掘这个置换 $g$ 的性质（$g^{-1}$ 与 $g$ 性质相同），手玩可以发现所有置换环大小都是 $2$ 在 $2(m-1)$ 下的阶 $r$ 的因数。
也就是答案关于 $r$ 是循环的，那么我们将大小相同的置换环加和之后，直接维护 $k\in[0,r)$ 的答案就好了。
复杂度 $O(nd(n)+q)$，可以通过。
## [D2T2 计算几何](https://www.luogu.com.cn/problem/P8333)
首先进行一步转化，去掉所有坐标为偶数的点，将相邻的点连接成一个三角形点阵，它的对偶图每条边恰好可以对应回原图每个点，其最大匹配即为原图最大独立集。
通过霍尔定理可以观察出一定存在完美匹配！然后就是 [P8114 [Cnoi2021]六边形战士](https://www.luogu.com.cn/problem/P8114) 了。[AC](https://www.luogu.com.cn/record/75271219)
## [D2T3 深搜](https://www.luogu.com.cn/problem/P8334)
离散化，枚举一个 $i$，令权值大于等于 $i$ 的点为黑点，那么我们就是要支持将一个点由黑染白，以及维护简单路径只经过黑点的点对，dfs 时不遇到白点的概率之和。
考虑将子树内有白点的点叫灰点，那么可以发现我们不能 dfs 入没有 $y$ 的灰点子树。转移方程大概长这样：（令 $s(x)$ 为 $x$ 的灰儿子数量）
$$f_x=\begin{cases}0&[x\ \text{is}\ \text{white}]\\\sum_{y\in son(x)}\begin{cases}\frac{f_y}{s_x}&[y\ \text{is}\ \text{grey}]\\\frac{size_y}{s_x+1}&\text{otherwise}\end{cases}\end{cases}$$
这样我们就得到了一个 $O(n^2)$ 的解法。
直接将转移方程刻画成矩阵，每次加入白点的时候暴力更新非灰的祖先（更新单点的转移系数以及一条链的 $f$），用一个全局平衡二叉树就是 $O(n\log n)$ 了。