做题笔记 2023.2

CF808G Anthem of Berland

我们也可以允许匹配过程随时中止，然后钦定问号为期望的字符，这样可能会求出一些错误答案，但错误答案只会比正确答案小，所以不影响，在完成匹配时要更新所有 border 的答案，这样做正确性不是那么显然，复杂度优化至 $O(|S|\cdot|T|)$。

CF702F T-Shirts

买衣服的过程很复杂，考虑把人丢到数据结构内，按顺序枚举每件衣服进行修改。

相当于要维护这样的操作：对于所有 $\ge c$ 的数，将它们减 $c$。

在平衡树上，我们可以拿出 $\ge c$ 的部分打减 $c$ 的标记，但是问题在于 $[c,2c)$ 这部分数在原树上的顺序被破坏，无法直接合并回去。考虑将这部分数暴力插入平衡树，这样做的复杂度是正确的，因为一个数每被暴力插入一次，值至少减半，故最多被减 $\log V$ 次。

总复杂度为 $O(n\log n\log V)$。

CF1100F Ivan ans Burgers

前缀线性基模版题，可以 $O(n\log n)-O(\log n)$ 的解决区间任意个数最大异或和问题。

具体的，对每个前缀维护一个线性基，线性基内每一位记录一个 pos 表示此处的数在序列上的位置，每次插入，我们从大到小遍历线性基的每一位，如果当前数能插到这个地方且 pos 比原 pos 大，就交换两个数，并将原数异或当前数，拿着原数继续往下遍历。

我们达到的效果是，优先使得较大的位 pos 尽量大。

每次查询找到 $[1,r]$ 对应的线性基，线性基内只有 $pos\ge l$ 的数可用，然后正常计算答案即可。

LG8511 [Ynoi Easy Round 2021] TEST_68

考虑找到全局异或和最大的两个点，那么除了这两个点到根路径上的点之外，所有点的答案都是这个最大值。

对于两条到根路径上的点，暴力计算答案即可，这部分每个点只会被插入 01trie 内 $O(1)$ 次。

总复杂度为 $O(n\log n)$。

LG6072『MdOI R1』Path

由于一条路径的权值为路径上边权的异或和，我们维护每个点到根路径上边权的异或和，那么异或两个点就可以得到两点之间路径的权值。

另外，两条不交路径一定可以会被某个点分开，一条在该点的子树内，一条在子树外，考虑枚举每个点，计算子树内的两数最大异或和加上子树外的最大异或和，最后取最大值即可。

那么用上一题的方法就做完了本题的一半。

对于子树内，我们可以用 dsu on tree 做到 $O(n\log^2 n)$。

当然，注意到除了两条到根路径上的点之外，所有点子树外的答案都相同，为了让子树内答案更大，显然这个子树越大越好，那么我们只需要暴力计算两条路径上点所有儿子子树内的答案即可，每个点依然只会被插入 01trie $O(1)$ 次，总复杂度为 $O(n\log n)$。

CF464D World of Darkraft - 2

期望妙妙题。

每件装备相同且独立，考虑对每件装备单独计算答案。

注意到一件装备被升到 $t$ 级的概率是 $\frac 1k\prod_{i=1}^t\frac1{t+1}$，这玩意减小速度极快，类似于生日悖论，由于答案用小数输出，允许一定的误差，所以我们不需要考虑过高的等级，具体来说，取等级上限在 $600$ 左右就已经足够了，也可以稳妥起见更大一点。

然后是常规的期望 dp。注意期望 dp 倒着做更简单。

CF464E The Classic Problem

很早以前的模拟赛题。

主席树维护高精度即可，需要支持的操作有：比大小，单点修改 / 区间覆盖，找到某个位置之前的第一个 0。

主席树上也可以直接打 lazytag，但是 pushdown 的时候要新建结点，这样做的复杂度没有任何问题。

比大小和找 0 都可以通过维护哈希值解决，哈希用于判断两个区间是否相等以及一个区间是否全是 1，实现有少量细节，不多赘述。

这题可以直接用题目要求的大质数取模作为哈希，这样还不用特意去求值。

LG5826 子序列自动机

子序列自动机是个很平凡的东西，就是贪心的匹配靠前的字符，子序列自动机维护每个位置之后每个字符第一次出现的位置即可。

LG6239 [JXOI2012] 奇怪的道路

首先我们要求每个点只能向前连边。

设 $f_{i,j,S}$ 表示已经考虑了前 $i$ 个点，连了 $j$ 条边，$S$ 表示 $[i-k+1,i]$ 这 $k$ 个点的奇偶性状态，在此情况下的方案数。

刷表转移，枚举第 $i+1$ 个点出发的连边改变了哪些点度数的奇偶性，还需要枚举连了多少条重边，重边不会改变点度的奇偶性，计算方案时要考虑每组重边连到了哪个点上，乘上一个组合数即可。

细节比较多。

神奇纸牌

转化后的一句话题意：$n$ 行 $4$ 列的 01 矩阵，对于每一行我们将值为 $1$ 的列合并起来，若最终所有列都被合并在一起，求初始矩阵的方案数。

这类连通性计数问题通常和斯特林数 / 斯特林反演有关。

考虑容斥，设 $f(k)$ 表示钦定这 $4$ 列被分为 $k$ 个连通块（也就是说，只在钦定的连通块内连边，很显然，有可能连通块个数大于 $k$），$g(k)$ 表示连通块个数恰为 $k$ 的方案数，有：
$$
f(k)=\sum_{i=k}{i\brace k}g(i)
$$
因为连通块是无序的，所以会出现第二类斯特林数。接下来可以递推求解，也可以使用斯特林反演。
$$
g(k)=\sum_{i=k}(-1)^{i-k}{i\brack k}f(i)
$$
形式和二项式反演不能说非常相似只能说一模一样。目前还没有系统学过斯特林数相关的内容，而且多项式的技能树才刚开始点，要学的东西还不少。

打扫笛卡尔

转化后的一句话题意：定义树上一个点的权值为 $\dfrac{dep}{2^{dep-1}}$，对所有 $n$ 的排列建出笛卡尔树，求 $n!$ 棵树上所有点的期望权值和。

设 $[x^k]F_n(x)$ 表示所有 $n$ 的排列对应的笛卡尔树中深度为 $k$ 的点的个数，于是：
$$
F_i(x)=\sum_{j=0}^{i-1}\left(xF_j(x)\binom{i-1}{j}(i-1-j)!+xF_{i-1-j}(x)\binom{i-1}{i-1-j}j!\right)+i!x
$$
即，考虑枚举左子树点数。边界是 $F(0)=0$。

发现和式内的部分是对称的，所以可以重新整理：
$$
F_i(x)=2\sum_{j=0}^{i-1}xF_j(x)\binom{i-1}{j}(i-1-j)!+i!x
$$
我们最后要求的是 $\sum_i \dfrac{i}{2^{i-1}}[x^i]F_x(x)$，观察我们的转移，每当 $x$ 的指数增加 $1$，系数就会同时乘 $2$，所以我们可以干脆把分母上二的幂以及转移方程中的乘二一起去掉。

剩下的内容就是拆开组合数和阶乘，变变形，前缀和优化转移，复杂度线性。

CF1785C Monsters (hard version)

对于一个不降的序列 $a_{1\dots n}$，我们会希望将它最终变为 $1,2,\dots, n$，当然其中存在一些无效点，它们可以保持与上一个点相同的取值。

具体来说，设 $f(i)$ 表示满足 $a_k\le i$ 的 $k$ 的个数，如果序列中原本不存在无效点，现在我们加入一个点，这样最多会产生一个无效点，并且不难发现这个无效点是满足 $f(a_i)>a_i$ 的最小的 $a_i$。

可以用值域线段树（维护 $f(i)-i$）或平衡树找无效点并删除，或者对于每个 $i$ 维护 $f(i)$ 变为 $i$ 的时间，这样的点我们称之为饱和，每次插入 $a_i$，找到第一个大于等于 $a_i$ 的饱和点，这个点将会被删除。

CF715E Complete the Permutation

很有意思的一道题。

简单来说，我们知道将一个长度为 $n$ 的序列排成某种顺序需要的交换次数（交换任意两个数）为 $n$ 减去循环个数。为了方便计数，我们要将这里的循环用图论模型来描述。我个人倾向于将原序列和目标序列视作一个二分图，左边只能向右边相同的位置连边，而从右边出发的边指向左边相同的数。当然，连边方式有很多种，怎么方便思考怎么来。

这样的话，对于一个残缺的序列，我们会连出若干完整的环和若干残缺的环。对于一个残缺的环，在这个特殊的模型中，也就是一条链，我们发现其一定等价于一个孤立点或单独的一条边。我们将完整的环去除，将链缩成孤立点和边，图中就只剩下了：

孤立点，且左右两侧个数必然相等
从左向右的连边（简称 AB 边）
从右向左的连边（简称 BA 边）

不难发现，AB 边和 BA 边是绝对不会出现在一个环内的，我们先让孤立点和若干 BA 边（还有一些 BA 边自己拼成了环）组合形成 AB 边，然后让所有 AB 边组合，按这个顺序计数即可。

upd on 2023.3.28：这种二分图连边方式其实不太方便，如果使用的话一定注意，左向右连的边一定位置相同，右向左连的边一定值相同，思考的时候可以认为右边的点是完全不区分的（用连入的边确定位置，连出的边确定值）（那和 $p_i\to q_i$ 有啥区别 /fad）。

CF1681F Unique Occurrences

考虑单独计算每种颜色的贡献。

某种颜色的边需要经过恰好一次，那么我们删去树上所有这种颜色的边，一条边的贡献就是树上两个相邻连通块大小的乘积。

线段树分治即可。除此之外还可以建虚树 dp 或直接在原树上换根 dp。

LG2664 树上游戏

对于这种数颜色问题，我们考虑计算每种颜色所作出的贡献。

大规模路径问题，考虑点分治。计算子树内结点对分治中心的贡献是平凡的，问题在于我们如何计算跨越分治中心的路径对一个端点的贡献。

对于每种颜色 $c$ 我们统计 $cnt_c$ 表示当前分治中心的子树内有多少结点到分治中心的路径上包含颜色 $c$，然后对于一条跨越分治中心的路径，我们将其在分治中心处断开，两部分分别计算贡献即可。

Topcoder 13444 CountTables

斯特林反演模版题。

我们钦定行的限制被满足，然后对列的限制进行容斥。注意这里为什么会出现斯特林数，因为「列」这个结构自带顺序，所以我们只需要进行等价类的划分，然后按照天然的顺序构造双射即可。

GYM100517C Comb Avoiding Trees

满二叉树计数有一种奇妙的方法，即按照先序遍历顺序 dp，由于满二叉树的性质，从一个点到下一个点，只可能是走向左儿子或者退回上一个走向左儿子的点走向右儿子。

这道题用这种方式就可以做到 $O(n^2)$。我也不知道这个东西有没有广泛的适用性。

值得一提的是本题还能够做到线性单点求值，具体来说，我们的 dp 方程可以视作一个括号序列 / 格路计数模型，然后容斥即可。

CF765F Souvenirs / CF1793F Rebrending

区间一维最近点对的模版题。

考虑对前 $r$ 个数维护 $f_i$ 表示 $|a_i-a_j|,i<j\le r$ 的最小值，每次相当于查询 $f_i$ 的后缀最小值。现在我们希望从 $r$ 转移到 $r+1$，那么我们需要计算前面数与 $a_{r+1}$ 对答案的贡献，为了方便起见，下面就让 $r\gets r+1$。不难发现对于 $a_r$ 同侧的两个点，不妨设 $a_i,a_j\ge a_r,i<j<r$，如果 $a_j$ 用 $a_r$ 更新了答案，那么 $a_i$ 会有必要用 $a_r$ 更新答案当且仅当 $a_i<\dfrac{a_j+a_r}2$，否则 $a_i$ 与 $a_j$ 的答案更优。

按照上面的思路，有两种实现方法，一种是先只考虑 $a_r$ 单侧的答案，然后将整个序列的值取反再做一次，用一颗权值线段树查询当前序列中最靠后的 $\le x$ 的数的位置，通过不断缩小值域找出所有需要更新的点即可，两个 $\log$。另一种做法是直接用线段树维护序列，每次修改先走右儿子再走左儿子，如果发现当前结点对应区间的答案劣于右侧的最小值就直接 return，可以证明这样做是三个 $\log$ 的。

LG2597 [ZJOI2012] 灾难

支配树模版题。这题的题解质量真的是够低的。

首先，给定起点 $s$，如果删去 $x$ 后 $s$ 无法到达 $y$，则称 $x$ 支配 $y$，也即，$x$ 是 $s$ 到 $y$ 的必经之路。

在支配树上，每个点的父亲是距离自己最近的支配点（不难发现不会有两个支配点到自己的距离相同），这里距离定义为最短距离或者什么别的东西都行，所有祖先是自己所有的支配点，子树内是被自己支配的点。

求支配树，我们考虑按照拓扑序，即每次找到入度为 0 的点，将其加入支配树，其父亲应该是所有入边起点在支配树中的 lca，这里求 lca 其实是对这些点的支配点集合取了个交，由于要支配树是由上到下逐步构造的，求 lca 最方便的方法是直接倍增，复杂度为 $O(n\log n)$。

LG5513 [CEOI2013] Board

初看这道题我的思路是用类似 The Classic Problem 的方法，通过线段树快速维护高精度二进制数，当然本题并不需要这么复杂。

由于我们是先进行了若干次修改，然后在进行查询，我们没有必要动态的维护高精度数，具体来说，每次进行加减饭我们并不进行进位 / 借位，当前位无论是 $\ge 2$ 或 $<0$ 我们都将其留在原地，如果需要右移则只处理最低的两位，最后统一将所有位修正，相当于一种 lazy 的思想。

这样复杂度是线性的。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Catalog