ZJOI 选做

[ZJOI2015]地震后的幻想乡

考虑克鲁什卡尔的算法流程,发现最小生成树之和相对大小关系相关,由于是实数期望,所以可以忽略掉大小关系相等的情况。一种简单的方法就是枚举 \(m\) 条边的相对大小关系,然后模拟克鲁什卡尔算法,假设在第 \(i\) 条边加入时联通,那么答案为 \(\dfrac{i}{m+1}\),因此设 \(f_i\) 表示加入 \(i\) 条边时仍然没有联通的方案数,那么答案为 \(\dfrac{1}{m+1}\sum \dfrac{a_i}{\binom{m}{i}}\)。因此只需要快速求出 \(a_i\) 即可。

设 \(f[i][j]\) 表示集合 \(i\) 中连接了 \(j\) 条边,联通的方案数,那么 \(a_i=1-f[M][i]\)。接下来就是常规操作了,固定最小的点 \(p\) 必须被包含,那么 \(f[S][i] = 1-\sum_{T\in S, 2^p\in T}f[T][j]\times \dbinom{cnt_{T\&S}}{i-j}\),直接转移即可,复杂度 \(O(3^n\times m)\),当然可以采用子集卷积进行优化,但是实际效率可能会更慢。

[ZJOI2016]大森林

查询操作可以在修改之后统一完成,我们只要能还原出最后的每一棵树即可。然后相邻的两棵树的关系一定是十分密切的,考虑依次枚举每一棵树,然后还原出当前这棵树。

我们从 \(1\to n\) 枚举每一棵树,然后可以发现只有 \(4\) 种操作:删除一个操作 \(0\),增加一个操作 \(0\),删除一个操作 \(1\),增加一个操作 \(1\)。

对于操作 \(0\),实际上把每个操作 \(0\) 当成 \([1, n]\) 也没有问题,因为操作 \(1, 2\) 都不会操作不存在的点。只需要在操作 \(1\) 的时候判断其合法性即可,由于每次操作都是一段区间,所以可以将删除/加入一个 \(0\) 操作看成删除/加入一些 \(1\) 操作,由于总量是 \(O(M)\) 级别的,所以只需要处理 \(1\) 操作即可。

考虑两次操作 \(0\) 之间的所有修改操作,他们都是一类点,我们可以建一个虚点,然后每次增加或者删除 \(1\) 操作就是直接将虚点的父亲改掉即可。然后我们用一个点存储他到父亲节点的边是否存在,注意这里不能直接 \(spilt\),需要求出 \(LCA\),然后统计 \(dep\),\(LCA\) 即先 \(access(x)\) 之后再 \(access(y)\) 第一个通往 \(x\) 的那个点。

[ZJOI2016]小星星

先考虑一个暴力,考虑这是一棵树,我们考虑树形\(Dp\),直观的想法是设\(dp[i][j][k]\)表示考虑到以\(i\)为根的子树,在图中映射出来的点集为\(j\),且当前\(i\)号点所映射的点为\(k\)的方案数。转移比较显然,对于每个\(u\),枚举一个子树内选择的点的子集即可。这里的复杂度是\(O(3^NN^3)\)的,\(N^3\)分别来自枚举根节点,枚举根节点和子树分别选择什么,可以通过\(FWT\)优化到\(O(2^N N^4)\),还不能通过此题。

考虑到\(i, k\)是省不掉的,而且这个范围也不难猜到复杂度跟\(O(2^N)\)有关,我们尝试优化掉\(j\)这一维。

我们需要保证每个点恰好需要用一次,才导致于我们必须要记录 \(j\) 这一维,那如果不限制这个,可以任意选择呢?可以发现,我们 \(2^n\) 枚举所有子集,强制规定树上的映射只能选择这个子集内的点,发现 \(j\) 这一维突然消失了,然后所求得的答案对最终答案的贡献就是\((-1)^{n-|S|}\)。于是我们的复杂度就变成了\(O(N^3\times 2^N)\),由于我们只能选择一个子集,大概可以带一个\(\dfrac{1}{4}\)的常数,于是我们可以通过此题。

[ZJOI2016]旅行者

考虑分治,假设当前分治矩形长宽分别为 \(a\times b\),且 \(a>b\),那么我们将其分成两个矩形,大小为 \(\dfrac{a}{2}\times b\)。然后求出边界上每个点到其他所有点的最短路,对于一个询问,如果其两个点都在其中一个矩形中或者分在了两个矩形中,那么就更新一下答案,不难计算复杂度为 \(O((S+Q)\sqrt{S}logS)\)。

[ZJOI2017]线段树

找到 \([l, l]\) 与 \([r, r]\) 的 \(LCA\),抛开这一层,暴力递归到下一层去,然后将询问拆分成 \([l, x], [x+1, r]\),那么询问就变成了一个区间的前缀或者后缀。不妨只考虑前缀,后缀也可以用类似的方法进行求解。

考虑求出 \([r, r]\) 与 \(u\) 的 \(LCA\),简单画图+分类讨论可以得出,我们只需要支持查询 \([l, r]\) 的节点个数即可求出答案,很显然只需要深度做差即可。

[ZJOI2017]仙人掌

题意可以转化成:给定一棵树,有一些已经选择的链,你再选择若干条长度大于 \(2\) 的链,使得其没有公共边。然后不难发现,只要去掉所有的环,那么原图会变成一个森林,森林之间互不影响,求出每个数的答案相乘即为答案,所以我们只需要可以计算出树的答案即可。

考虑怎么计算一颗树的方案数,有一个神奇的转化:考虑一个合法的方案,我们把所有的非环上的边看成一条重边,也就是一个环,那么原问题可以转化成:给定一棵树,求有多少种方案,选择若干条链覆盖所有边,且所有链边互不相交。为什么是对的呢?环的长度一定大于等于三,而没有被覆盖的边如果把他看成长度为 \(2\) 的环,那么所有的边都会被恰好覆盖一次,且我们对链而的长度没有了限制!

考虑转化题意要怎么进行计算,先把所有的边看成是一条链,那么对于每个点,他可以选择连接两条链,也可以不连接,我们设其度数为 \(d_i\),设 \(f_i\) 表示 \(i\) 叶子结点的菊花图的答案,那么根据乘法原理,答案为 \(\prod f[d[i]]\),至于 \(f_i\) 的计算,枚举其是否匹配,易得 \(f_i=f_{i-1}+f_{i-2}\times (i-1)\)。

[ZJOI2017]树状数组

首先题意可以转化成:给一段区间的一个数等概率异或一,查询两个点相等的概率。

不难想到,我们可以将区间分为三类:只包含第一个点的,只包含第二个点的,包含两个点的。其余区间对答案没有影响。

可以先考虑一个暴力 \(dp\),设 \(dp[i][0/1]\) 表示考虑到第 \(i\) 次修改,当前节点是 \(0/1\) 的概率,然后转移比较显然,只和区间长度相关。如果我们将一个区间的左右端点 \((l, r)\) 看成二维平面上的一个点,那么我们对答案有影响的三类区间分别在三个矩形中,那么我们只需要快速维护矩形的 \(dp\) 值即可。可以用 \(KDT\) 来实现,每个节点存的是只考虑这个节点所包含的点的 \(dp\) 值。

[ZJOI2018]历史

首先对于每个点分开考虑,这个点对答案的贡献考虑怎么计算。

首先每个点的每一个儿子的子树,对根节点的贡献是一样的。所以,每一个点对答案的贡献只跟:当前点的\(a_i\)以及所有儿子的子树\(a_i\)之和有关

假设所有有关的值的最大值为\(Ma\),和为\(Sz\),那么这个点对答案的贡献是:\(Sz-max(0, 2\times Ma-Sz-1)-1\)(-1是因为最开始占领需要花费一次)。\(Sz-1\)很好维护,所以我们现在只需要考虑怎么维护\(max(0, 2\times Ma-Sz-1)\)

以下是神仙操作:

考虑两种情况对答案的贡献,第一种情况是\(2\times Ma \ge Sz+1\),发现这种\(Ma\)最多只有一个。于是我们可以类似\(LCT\),把所有满足这个条件的点和其父亲连重边,其余连轻边,不难发现仍然满足\(LCT\)的性质。

考虑每一次修改,我们对其路径上的点进行修改,重链修改的部分只有可能是把路径上的一条轻链变成重链。这样的修改最多是\(log\)个,暴力修改即可

[ZJOI2019]语言

考虑一个点可以到达的点一定是以下方式构成:考虑所有经过他的链,然后这些链的端点所形成的连通块,即为一个点所有可以到达的点。假设求出了这些点,可以通过建立虚树的方式求出连通块大小。

考虑具体的计算方式,将所有关键点按照 \(dfs\) 序排序,每个关键点对答案的贡献为他到上一个关键点的 \(LCA\) 的距离,因此我们可以很方便的支持插入/删除一个关键节点。

考虑一个点 \(u\) 的所有关键点和儿子节点的所有关键点之间的关系,不难发现就是先取并集,然后加上起点在点 \(u\) 的点,计算答案之后,减去起点和终点均在 \(u\) 子树内的链(也就是 \(LCA\) 为 \(u\) 的链),再合并上去,用启发式合并可以简单做到 \(O(Nlog^2N)\)

[ZJOI2019]开关

设\(f_i\)表示状态为\(i\)的期望步数,那么我们考虑转移方程:

\[f_i=\sum_{k}f_{i\oplus 2^k}\times p_{k}+1=\sum_{j\oplus k=i}f_{j}\times p_{k}+1 \]

其中\(p_{k}\)只在\(2^k\)处为\(p_k\),其余部分为\(0\)。

然后我们可以利用高斯消元来求解,复杂度\(O(8^n)\),我们还需要进行优化。

考虑设\(F(x)=\sum_{i=0}^{n}f_ix^i, G(x)=\sum_{i=2^k}p_kx^i, I(x)=\sum_{i}x^i\)。所以我们可以写成:\(F(x)=F(x)\times G(x)+I(x)+c\),其中\(+c\)的意义是强制把\(f_0\)转成\(0\)。

接下来是一步神奇的操作,这里实际上是一个异或卷积,我们可以把它们强行转成点值,于是我们有:\(FWT_i(F(x))=FWT_i(F(x))\times FWT_i(G(x))+FWT_i(I(x))+FWT_i(c), FWT_i(F(x))(1-FWT_i(G(x)))=FWT_i(I(x))+FWT_i(c)\)。不难发现这些点值都很有规律。

\(1.FWT(C)\)

不难发现他恒等于\(c\)。

\(2.FWT_i(I(x))\)

设\(i\)有\(k\)个\(1\),考虑\(FWT_i=\sum_{j}(-1)^{|i\&j|}=2^{n-k}\sum_{j=0}^k\dbinom{k}{j}(-1)^j=2^{n-k}[k==0]\)。

\(3.FWT_i(G(x))\)

\(FWT_i(G(x))=\sum_{j}(-1)^{|i\&j|}\),也就是所有\(0\)位置上的\(p_j\)之和减去\(1\)位置上的\(p_j\)之和。

当\(i=0\)时,\(FWT_i(G(x))=1\),所以此时\(-FWT_i(I(x))=FWT_i(c)\),所以我们解出\(c=-2^n\)。

我们先考虑\(i=0\)。\(i=0\)时上面的方程不能计算,但由于\(IFWT_0(FWT_0(F(x)))=0\),所以\(FWT_0(FWT_0(F(x)))=0\),即\(FWT_0(F(x))=-\sum_{i\ne 0}{FWT_i(F(x))}\),算出所有的\(FWT_i(F(x))\)之和即可。

\[FWT_i(F(x))=\dfrac{-2^n}{1-FWT_i(G(x))}=\dfrac{-2^n}{2\times \sum_{i\&{2^k}\ne 0}p_k} \]

\[\begin{aligned}&\;\;\;\;IFWT_i(FWT_i(F(x)))\\&=\dfrac{1}{2^n}\Big(\sum_{j\ne 0}(-1)^{|i\&j|}\dfrac{-2^n}{2\times \sum_{i\&{2^k}\ne 0}p_k}+\sum_{j\ne 0}\dfrac{2^n}{2\times \sum_{i\&{2^k}\ne 0}p_k}\Big)\\&=\Big(\sum_{j}\dfrac{|i\&j|≡1\;mod\;2}{\sum_{i\&{2^k}\ne 0}p_k})\end{aligned} \]

到这里我们已经有一个\(O(2^n)\)的做法了,考虑怎么加速这个计算过程:设\(dp[i][0/1][j]\)表示考虑了前\(i\)个数,和\(S\)集合的交集的奇偶性为\(0/1\),当前的\(p_i\)之和为\(k\)的方案数。直接转移即可,复杂度\(O(n\sum P)\)。

上一篇:CF613A 扫雪机


下一篇:Codeforces 446C - DZY Loves Fibonacci Numbers(斐波那契数列+线段树)